Knapsack Problem

Posted on | In

Knapsack Problem

0-1 Knapsack Problem

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and weight[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).

We can use dynamic programming to solve this problem. We create a 2 dimensional array dp[i][j] which represents the the maximum value we can make by putting the first i item in a knapsack with j capacity. We have:

  • dp[i][0] = dp[0][j] = 0
  • dp[i][j] = dp[i-1][j] if weight[i] > j
  • dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + val[i]) if j >= weight[i]

Using two dimensional array:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Main {
    public static void main(String[] args) {
        int[] weight = { 3, 5, 2, 6, 4 };
        int[] val = { 4, 4, 3, 5, 3 };
        int W = 12;
        int n = val.length;

        int[][] dp = new int[n + 1][W + 1];
        int[][] path = new int[n + 1][W + 1];
        // intialize the first row and column
        // no need to fill full the knapsack
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = 0;
        }
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }
        // dynamic function
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (weight[i - 1] > j)
                    dp[i][j] = dp[i - 1][j];
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + val[i - 1]);
                }
            }
        }

        // stores the result of Knapsack
        int res = dp[n][W];
        System.out.println("Maximum value " + res);

        int w = W;
        // check if the last row has the same result
        for (int i = n; i > 0 && res > 0; i--) {
            if (dp[i - 1][w] == res)
                continue;
            else {
                System.out.println("Choose the " + i + "th item.");
                res = res - val[i - 1];
                w = w - weight[i - 1];
            }
        }
    }
}

Output:

1
2
3
4
Maximum value 12
Choose the 4th item.
Choose the 3th item.
Choose the 1th item.

Using one dimensional array. In the inner loop, we loop backward because it makes sure that when we are calculating dp[j], we already have the result for dp[j-weight[i]], in other words, which is the result for dp[i-1][j-weight[i-1]]. If we loop forward, that will be dp[i][j-weight[i-1]].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Main {
    public static void main(String[] args) {
        int[] weight = { 10, 20, 30 };
        int[] val = { 60, 100, 120 };
        int W = 50;
        int n = val.length;

        int[] dp = new int[W + 1];

        // no need to fill full the bag
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 0;
        }

        for (int i = 0; i < n; i++) {
            for (int j = dp.length - 1; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + val[i]);
            }
        }

        System.out.println("Maximum value " + dp[dp.length - 1]);
    }
}

Output:

1
Maximum value 220

If we need to fill full the knapsack, then initially dp[0] = 0, dp[1..W] = -∞ because if W=0 that means we can put an item that has weight 0 to the knapsack to fill up its weight, in other words, we don’t need to put any item into the knapsack and it’s legal, so the maximum value will be 0. Other W doesn’t have a solution, so they are undefined, so we initialize them to INT_MIN.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Main {
    public static void main(String[] args) {
        int[] weight = { 3, 5, 2, 6, 4 };
        int[] val = { 4, 4, 3, 5, 3 };
        int W = 12;
        int n = val.length;

        int[] dp = new int[W + 1];

        // need to fill full the bag
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Integer.MIN_VALUE;
        }

        for (int i = 0; i < n; i++) {
            for (int j = dp.length - 1; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + val[i]);
            }
        }

        System.out.println("Maximum value " + dp[dp.length - 1]);
    }
}

Output:

1
Maximum value 11

Complete Knapsack Problem

In Complete Knapsack Problem, for each item, you can put as many times as you want. Therefore, if capacity allows, you can put 0, 1, 2, … ∞ items for each type.

To solve it, we can just change the above solution’s inner loop order to forward.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Main {
    public static void main(String[] args) {
        int[] weight = { 3, 4, 6, 2, 5 };
        int[] val = { 6, 8, 7, 5, 9 };
        int W = 10;
        int[] dp = new int[W + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 0;
        }
        for (int i = 0; i < val.length; i++) {
            for (int j = weight[i]; j < dp.length; j++) { // loop forward
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + val[i]);
            }
        }
        System.out.println("Maximum value " + dp[W]);
    }
}

Output:

1
Maximum value 25

Source:

背包问题(01背包和完全背包)java求解