Step 5 of 6
The 0/1 knapsack
A thief's bag holds a limited weight. Each item has a weight and a value, and each item can be taken once or not at all (that's the "0/1"). Which items give the most value without going over the limit? The same problem shows up as picking features for a release within a time budget, or choosing ads within a size limit.
Greedy fails again: taking the most valuable item first, or the best value per kilogram first, can leave awkward space unused. DP tries both choices for every item, once per remaining capacity.
The table
Let best[i][w] be the most value you can get from the first i items with capacity w. For item i (weight wt, value val) there are two choices:
- Skip it:
best[i - 1][w]. - Take it (only if
wt <= w):val + best[i - 1][w - wt], the item's value plus the best use of the capacity that's left, using only the earlier items.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> weight = {1, 3, 4, 5};
std::vector<int> value = {1, 4, 5, 7};
int cap = 7;
std::size_t n = weight.size();
std::vector<std::vector<int>> best(n + 1, std::vector<int>(cap + 1, 0));
for (std::size_t i = 1; i <= n; i++) {
for (int w = 0; w <= cap; w++) {
best[i][w] = best[i - 1][w]; // skip item i
if (weight[i - 1] <= w) // or take it
best[i][w] = std::max(best[i][w], value[i - 1] + best[i - 1][w - weight[i - 1]]);
}
}
std::cout << "best value: " << best[n][cap] << "\n";
}
best value: 9
The best choice is the items of weight 3 and 4 (value 4 + 5 = 9). Taking the most valuable item first (weight 5, value 7) leaves room only for the weight-1 item, for a total of 8.
One row is enough
Each row only reads the row above it, so a single 1D array can replace the whole table, if you loop over the capacity downward:
std::vector<int> best(cap + 1, 0);
for (std::size_t i = 0; i < n; i++)
for (int w = cap; w >= weight[i]; w--)
best[w] = std::max(best[w], value[i] + best[w - weight[i]]);
Going downward means best[w - weight[i]] hasn't been updated for item i yet: it still holds the "earlier items only" value, just like the row above in the 2D table. Looping upward would let an item be taken twice (once at w - weight[i], then again at w), which is the unlimited version of the problem, like the coins in step 2.
Yes/no knapsacks
The same shape answers yes/no questions. "Can some of these numbers add up to exactly t?" uses a std::vector<bool> can(t + 1) with can[0] = true, and for each number x, loops w downward setting can[w] = can[w] || can[w - x].
Your turn: write can_partition(nums): can the numbers be split into two groups with equal sums? Every number goes into exactly one group, and an empty list can be split (two empty groups). Numbers are positive, up to 100 of them, each at most 100.