Question

Implement the dynamic algorithm of 0-1 knapsack problem in Java. The following table shows 10 items, their values and weights. The maximum weight capacity of the knapsack is 113. What could be the maximum value of the knapsack and the most valuable set of items that fit in the knapsack?

Item	Weight	Value
1	32	727
2	40	763
3	44	60
4	20	606
5	1	45
6	29	370
7	3	414
8	13	880
9	6	133
10	39	820

Answer 1

The language used to solve this problem is Java. Algorithm implemented is dynamic programming.

Code:

public class KnapsackProblem {

    /**
     * Knapsack problem can be solved using dynamic programming.
     * Here, we have used bottom up approach.
     */
    public static int getMaxValueOfKnapSack(int maxWeight, int[] weightOfItems, int[] valueOfItems, int n) {

        int[][] knapsack = new int[n + 1][maxWeight + 1];

        // Fill the knapsack array
        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= maxWeight; w++) {
                if (i == 0 || w == 0) {
                    knapsack[i][w] = 0;
                } else if (weightOfItems[i - 1] <= w) {
                    knapsack[i][w] = Math.max(valueOfItems[i - 1] + knapsack[i - 1][w - weightOfItems[i - 1]], knapsack[i - 1][w]);
                } else {
                    knapsack[i][w] = knapsack[i - 1][w];
                }
            }
        }

        return knapsack[n][maxWeight];
    }

    public static void main(String[] args) {
        int[] weightOfItems = new int[]{32, 40, 44, 20, 1, 29, 3, 13, 6, 39};
        int[] valueOfItems = new int[]{727, 763, 60, 606, 45, 370, 414, 880, 133, 820};
        int maxWeight = 113;
        int n = valueOfItems.length;
        System.out.println("Maximum value of Knapsack: " + getMaxValueOfKnapSack(maxWeight, weightOfItems, valueOfItems, n));
    }
}

Code Snippet:

Sample Output for given input: