Backpack IV

Backpack IV (LI.562)

Given n items, an integer array sizes and a target, find the number of possible subsets of items to fill the backpack.

Example

I: sizes=[2,3,6,7], target=7
O: [ [2,2,3], [7] ] = 2

Notice: [2,3,2] and [3,2,2] are not taken into account

Analysis

Because we want subsets instead of combinations, this is a 0/1 knapsack problem.

Approach 1

1. Optimal subproblem
    kp[s] = maximum number of ways to fill size s
2. Recurrence
    if s < size[i]: kp[s] += 0 do nothing
    else if size[i] <= s: kp[s] += kp[s-size[i]]
3. Topo Order (0/1 is different from full)
    for i from 0 to n-1
        for s from 1 to target
4. Base case
    kp[0] = 1
    b/c there's only one way to fill an empty bag (no items [] subset)
5. Final answer
    kp[target]

State Graph 1

Code 1

public int backPackIV(int[] sizes, int target) {
    // create memo table
    int[] kp = new int[target + 1];
    // init base case
    kp[0] = 1;
    // topo order
    for (int i = 0; i < sizes.length; i++) {
        for (int s = sizes[i]; s <= target; s++) {
            kp[s] += kp[s-sizes[i]];
        }
    }
    // final answer
    return kp[target];
}

Approach 2

1. Optimal subproblems
    kp[i][s] = 
    maximum number of ways to fill out the target s with the first i items
2. Recurrence
    if sizes[i] <= s
        kp[i][s] += kp[i-1][s-sizes[i]]
3. Topo Order
    for i from 1 to n
        for s from 1 to target
4. Base case
    kp[0][s] = 0
    kp[i][0] = 1
5. Final Answer
    kp[n][target]

State Graph 2

Code 2

public int backPackIV(int[] sizes, int target) {
    // create memo table
    int n = sizes.length;
    int[][] kp = new int[n+1][target+1];
    // init base case
    for (int i = 0; i <= n; i++) {
        kp[i][0] = 1;
    }
    // topo order
    for (int i = 1; i <= n; i++) {
        for (int s = 1; s <= target; s++) {
            int k = 0;
            while (k*sizes[i-1] <= s) {
                kp[i][s] += kp[i-1][s-k*sizes[i-1]];
                k++;
            }
        }
    }
    // final answer
    return kp[n][target];
}

The recurrence below is wrong. It failed to enumerate all the occurrences of item i. Why does it differ from approach 1?

if (sizes[i-1] <= s) {
    kp[i][s] += kp[i-1][s-sizes[i-1]];
}