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.
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)
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];
}
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))
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).
