Practical session

public class Knapsack {

    public static int knapsackRecursive(int W, int[] weights, int[] values) {
        return knapsackRecursiveHelper(W, weights, values, weights.length);
    }

    private static int knapsackRecursiveHelper(int W, int[] weights, int[] values, int n) {
        // base case no items to check or no more space left
        if (n == 0 || W == 0) {
            return 0;
        }
        // if the current item is too heavy, skip it
        if (weights[n - 1] > W) {
            return knapsackRecursiveHelper(W, weights, values, n - 1);
        } else {
            // return the maximum of two cases:
            // 1. the current item is included
            // 2. the current item is not included
            return Math.max(values[n - 1] + knapsackRecursiveHelper(W - weights[n - 1], weights, values, n - 1),
                            knapsackRecursiveHelper(W, weights, values, n - 1));
        }
    }

    public static void main(String[] args) {
        // test case 1
        int W1 = 15;
        int[] weights1 = {12, 7, 11, 8, 9};
        int[] values1 = {24, 13, 23, 15, 16};
        System.out.println(knapsackRecursive(W1, weights1, values1)); // 28

        // test case 2
        int W2 = 30;
        int[] weights2 = {2, 3, 5, 7, 1, 4, 6, 8, 10, 9, 2, 3, 5, 7, 1};
        int[] values2 = {10, 15, 7, 8, 4, 12, 6, 11, 20, 18, 5, 9, 14, 16, 3};
        System.out.println(knapsackRecursive(W2, weights2, values2)); // 90
    }
}

public class Knapsack {

    public static int knapsackRecursiveMemo(int W, int[] weights, int[] values) {
        int n = values.length;
        int[][] table = new int[n + 1][W + 1];
        
        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                table[i][w] = -1;
            }
        }

        return knapsackRecursiveWithMemo(W, weights, values, n, table);
    }

    private static int knapsackRecursiveWithMemo(int W, int[] weights, int[] values, int n, int[][] table) {
        if (table[n][W] == -1) {
            if (n == 0 || W == 0) {
                table[n][W] = 0;
            } else if (weights[n - 1] > W) {
                table[n][W] = knapsackRecursiveWithMemo(W, weights, values, n - 1, table);
            } else {
                table[n][W] = Math.max(values[n - 1] + knapsackRecursiveWithMemo(W - weights[n - 1], weights, values, n - 1, table),
                                       knapsackRecursiveWithMemo(W, weights, values, n - 1, table));
            }
        }
        return table[n][W];
    }

    public static void main(String[] args) {
        int W = 50;
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        assert knapsackRecursiveMemo(W, weights, values) == 220;

        // Test case 1
        W = 15;
        weights = new int[]{12, 7, 11, 8, 9};
        values = new int[]{24, 13, 23, 15, 16};
        long start = System.nanoTime();
        System.out.println(knapsackRecursiveMemo(W, weights, values)); // 28
        System.out.printf("Time taken with memo: %.6f seconds%n", (System.nanoTime() - start) / 1e9);

        // Test case 2
        W = 30;
        weights = new int[]{2, 3, 5, 7, 1, 4, 6, 8, 10, 9, 2, 3, 5, 7, 1};
        values = new int[]{10, 15, 7, 8, 4, 12, 6, 11, 20, 18, 5, 9, 14, 16, 3};
        start = System.nanoTime();
        System.out.println(knapsackRecursiveMemo(W, weights, values)); // 28
        System.out.printf("Time taken with memo: %.6f seconds%n", (System.nanoTime() - start) / 1e9);
    }
}

import java.util.Arrays;

public class KnapsackDP {

    public static int knapsackDP(int W, int[] weights, int[] values, int n) {
        // Create a table to store the results of the subproblems
        int[][] table = new int[n+1][W + 1];
        // for each item in the list
        // the first row is for the case of no item, so we start at 1
        for (int i = 0; i <= values.length; i++) {
            // for each weight in the knapsack from W to the (weight in cell i) - 1
            for (int j = 0; j <= weights.length; w++) {
                // if the weight of the item is greater than the current weight
                // note that i starts at 1, so the weight of the item is weights[i-1]
                if(weights[i - 1] > j){
                    // the value is the same as the value without including the current item
                    table[i][j] = table[i - 1][j]
                }else{
                    // the value is the maximum of either including the current item or not including it
                    table[i][j] = max(table[i - 1][j], values[i - 1] + table[i - 1][j - weights[i - 1]])
                } 
            }
        }
        return table[n][W];
    }

    public static void main(String[] args) {
        // Test the function
        assert knapsackDP(50, new int[]{10, 20, 30}, new int[]{60, 100, 120}, 5) == 220;

        // test case 1
        int W = 15;
        int[] weights = {12, 7, 11, 8, 9};
        int[] values = {24, 13, 23, 15, 16};
        long start = System.nanoTime();
        System.out.println(knapsackDP(W, weights, values, 5)); // 28
        long elapsed = System.nanoTime() - start;
        System.out.printf("Time taken without memo: %.6f seconds%n", elapsed / 1e9);

        W = 30;
        weights = new int[]{2, 3, 5, 7, 1, 4, 6, 8, 10, 9, 2, 3, 5, 7, 1};
        values = new int[]{10, 15, 7, 8, 4, 12, 6, 11, 20, 18, 5, 9, 14, 16, 3};
        start = System.nanoTime();
        System.out.println(knapsackDP(W, weights, values, 15)); // 28
        elapsed = System.nanoTime() - start;
        System.out.printf("Time taken with memo: %.6f seconds%n", elapsed / 1e9);
    }
}

import java.util.*;

public class KnapsackGreedy {
    public static int knapsackGreedy(int W, int[] weights, int[] values) {
        // Create a list of items with value, weight, and value-to-weight ratio
        List<Item> items = new ArrayList<>();
        for (int i = 0; i < values.length; i++) {
            items.add(new Item(values[i], weights[i]));
        }
        // Sort the items by value-to-weight ratio in descending order
        items.sort((a, b) -> Double.compare(b.ratio, a.ratio));
        // Initialize the total value and the remaining weight
        int totalValue = 0;
        int remainingWeight = W;
        // Iterate through the items
        for (Item item : items) {
            // If the item can be included in the knapsack
            if (item.weight <= remainingWeight) {
                totalValue += item.value;
                remainingWeight -= item.weight;
            }
        }
        return totalValue;
    }

    static class Item {
        int value;
        int weight;
        double ratio;

        Item(int value, int weight) {
            this.value = value;
            this.weight = weight;
            this.ratio = (double) value / weight;
        }
    }

    public static void main(String[] args) {
        // Test the function
        int W = 50;
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        System.err.println(knapsackGreedy(W, weights, values));
//        assert knapsackGreedy(W, weights, values) == 220;
    }
}