Infinite Knapsack

Knapsack problem with unlimited supply of items.

Full Knapsack

You are given a knapsack with capacity C. There are n types of free items you can choose from. Each item has a weight and a value. Your goal is to stuff the bag and maximize the total value. Assume the supply for each item is unlimited.

Example

I: weights=[2,3,5,7], values=[1,5,2,4], capacity=10
O: 5+5+5 = 15

Approach

1. Optimal Subproblem
    kp(w) = maximal value with capacity w
2. Solve by prefix
    for all items that can fit in the bag
        kp(w) = Math.max(kp(w), value(j) + kp(w-weight(j)))
3. Topo Order
    for w from 1 to capacity
4. Base case
    kp(0) = 0 no space = no value
5. Final Answer
    kp(capacity)

Code (LI.440)

public int backPackIII(int[] weights, int[] values, int capacity) {
    // create memo table [0...capacity]
    int[] kp = new int[capacity + 1];

    // init base case
    kp[0] = 0;

    // topo order
    for (int w = 1; w <= capacity; w++) {
        // recurrence
        kp[w] = kp[w-1];
        for (int j = 0; j < values.length; j++) {
            if (w >= weights[j]) {
               kp[w] = Math.max(kp[w], values[j] + kp[w-weights[j]]);
            }
        }
    }

    // final answer
    return kp[capacity];
}

Time & Space Complexity

0/1 Knapsack

What if there's only one unit for each item?

Example

I: weights=[2,3,5,7], values=[1,5,2,4], capacity=10
O: 5+4=9

First Attempt

1. Optimal subproblem
    kp(i) = maximal value at ith item
2. Solve by prefix
    kp(i) = Math.max(???) how to decide whether to include this item?
    We need more information, namely the remaining capacity

Second Try

1. Optimal Subproblem
    kp(i,w) = maximal value at ith item with capacity w
2. Solve by prefix (2 choices or 2 edges)
    if (weight(i) <= w)
        kp(i,w) = Math.max(kp(i-1,w), kp(i-1,w-weight(i)) + value(i))
3. Topo order
    for i from 1 to n
        for w from 1 to capacity
4. Base case
    kp(0,w) = 0
    kp(i,0) = 0
5. Final answer
    kp(n,capacity)

Note that define/solve by suffix is also fine

suffix of i with w as the remaining capcity
kp(i,w) = Math.max(kp(i+1,w), kp(i+1,w-weight(i)) + value(i))

Code (LI.125)

public int backPackII(int capacity, int[] weights, int[] values) {
    // create memo table
    int n = values.length;
    int[][] kp = new int[n+1][capacity+1];

    // init base case

    // topo order
    for (int i = 0; i < n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i] > w) {
                // note kp[0][w] is 0 so kp is one item behind the item index
                kp[i+1][w] = kp[i][w];
            } else {
                kp[i+1][w] = Math.max(kp[i][w], kp[i][w-weights[i]] + values[i]);
            }
        }
    }

    // final answer
    return kp[n][capacity];
}

Pseudo-Polynomial Time

We successfully tried all possible subsets. What's the runtime then? #subproblem = O(n*capacity) and time/subproblem = O(1) so the total running time is O(n*capacity). Note that polynomial time means polynomial in n. But capacity is not. With a worst case of exponential time in n, this algorithm runs in pseudo-polynomial time.

Space Complexity

Right now, we are using a two dimensional array to store all the states. So the space complexity is O(n*capacity). There are two ways to optimize space. We can still define the subproblem the same way and realize that we only need 2 dependencies so we can compress the rows to 2. Or we can define the subproblems like how we did in the full knapsack problem, using just the weights. Either way, we will lose the ability to recover the subset of items (using parent pointer).

Space Optimization