There is a shop with N items, each with a different weight W and value V. We want to select some subset of these N items such that the sum of their values V is maximized and the sum of their weights W does not exceed some threshold C.
0/1 Knapsack: There exists only 1 of each item.
Let dp[i][j] be the maximum sum of values we can obtain if we only look at the first i items and the sum of their weights is j.
Then let’s say we process some item weight w_i, and value v_i. Then:
dp[i][j] = max(dp[i-1][j-w_i] + v_i) for all j >= w_i
In fact we can simplify the DP into one dimension as shown:
| int knapsack(vector<pair<int, int>> items, int cap){ //items.first = weight, items.second = value vector<int> dp(cap + 1); for(auto [w, v] : items){ for(int i = cap; i >= w; i–){ dp[i] = max(dp[i], dp[i – w] + v); } } return *max_element(dp.begin(), dp.end()); } |
Notice that the transition is the same as outlined above, simply reduced to one dimension.
Infinite Knapsack: There are an infinite number of items we can take.
The transition is very similar, except this time we can take an item multiple times.
For 0/1 Knapsack:
dp[i][j] = max(dp[i-1][j-w_i] + v_i) for all j >= w_i
For infinite:
dp[i][j] = max(dp[i-1][j-w_i] + v_i, dp[i][j-w_i]+v_i) for all j >= w_i
Now we process in increasing order of j for each i, and we can transition from dp[i] now to simulate taking an item multiple times.
| int knapsack(vector<pair<int, int>> items, int cap){ //items.first = weight, items.second = value vector<int> dp(cap + 1); for(auto [w, v] : items){ for(int i = w; i <= cap; i++){ dp[i] = max(dp[i], dp[i – w] + v); } } return *max_element(dp.begin(), dp.end()); } |
Notice that the code is very similar except that we reverse the order of the loop in order to allow us to use an item multiple times.
Limited Knapsack: An item appears a limited number of times.
Assume some item appears K times.
Naively, we can simulate the 0/1 knapsack idea K times. However, this is too slow.
In fact we can do a binary grouping optimization. For each power of 2 (call it j) that does not exceed K, we can “combine” the item j times together.
For example for j = 4, we can make a package with weight W_i * 4 and value V_i * 4.
Notice that if we do this for all powers of 2 less than K, we can combine these packages to form any number less than K, hence we can simulate taking the package any number of times. This has time complexity O(logK) instead of O(K), speeding up time a lot.