Knapsack Problem
The term knapsack refers to problems where a set of objects is given, and subsets with some properties have to be found. Knapsack problems can often be solved using dynamic programming.
Bottom-Up Knapsack (Iterative) in
How to think of the problem
Think of it like a bag of coins, where each coin has a weight, but each coin also has value (2, etc). You want to maximize the bag’s value while staying within the constraints of the weight.
Resources
When we do bottom-up dp, we do it in Topological Order.
0-indexed
int wt[n]; // Weights
int val[n]; // Value
int W; // Our capacity is given by W
int dp[n+1][W+1]; // We have n+1 because we want to be able to choose or NOT choose item (n-1), and our update is one step ahead
cin >> wt[i] // for 0...n-1
for (int i=0;i<=n;i++) {
for (int w=0;w<=W;w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else if (w - wt[i] >= 0) {
dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i-1]] + val[i-1]);
} else {
dp[i][w] = dp[i-1][w];
}
}
}
cout << dp[n][W] << endl; // Answer
In CS341, we saw a 1-indexed version, which to me is more intuitive
- The reason 1-indexed is much easier is because we have space for the base case. In the example above, we use 1-indexed for dp, but 0-indexed for the actual values, which makes it super confusing
- So in general, just use 1-indexed!!
- The issue is that arrays are generally 0-indexed if they already give it to you, which makes it kind of annoying
more generally
I find that 1-indexed is easier, due to setting up the base case at
i==0
.
1-indexed solution
int wt[n+1]; // Weights
int val[n+1]; // Value
int W; // Our capacity is given by W
int dp[n+1][W+1]; // We have n+1 because we want to be able to choose or NOT choose item (n-1), and our update is one step ahead
cin >> wt[i] // for 1...n
for (int i=0;i<=n;i++) {
for (int w=0;w<=W;w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else if (w - wt[i] >= 0) {
dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i]);
} else {
dp[i][w] = dp[i-1][w];
}
}
}
cout << dp[n][W] << endl; // Answer
Note:
The example above uses 0-indexing. If you use 1=indexing, you should use wt[i]
instead of wt[i-1]
;
Notice I use for example wt[i-1]
, and when we cin >> wt[i]
its from 0...n-1
. If you choose to do the update with wt[i]
, make sure to cin 1...n
, and then the update is for wt[i]
.
Optimized space. We need to go from W...0
because else the weights are going to be in different sizes.
// making and initializing dp array
int dp[W + 1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i < n + 1; i++) {
for (int w = W; w >= 0; w--) {
if (wt[i - 1] <= w) {
// finding the maximum value
dp[w] = max(dp[w], dp[w - wt[i - 1]] + val[i - 1]);
}
}
}
return dp[W]; // returning the maximum value of knapsack
Other Example
Given a list of weights , determine all sums that can be constructed using the weights.
We can recursively calculate this using the recurrence
possible[0][0] = true;
for (int k = 1; k <= n; k++) {
for (int x = 0; x <= W; x++) {
if (x-w[k] >= 0) possible[x][k] |= possible[x-w[k]][k-1];
possible[x][k] |= possible[x][k-1];
}
}
However, here is a better implementation that only uses a one-dimensional array possible[x]
that indicates whether we can construct a subset with sum x.
The trick is to update the array from right to left for each new weight:
possible[0] = true;
for (int k = 1; k <= n; k++) {
for (int x = W; x >= 0; x--) {
if (possible[x]) possible[x+w[k]] = true;
}
}