Knapsack Family

The classic: items have weights and values. Find max value fitting in capacity W. Each item used at most once.

dp[w] = max value achievable with capacity w

Key: Iterate capacity backwards to avoid using same item twice.

for (item : items)
    for (w = W down to weight[item])
        dp[w] = max(dp[w], dp[w-weight] + value)

`weights`	`values`	`W`	result	taken
`[1, 2, 3]`	`[6, 10, 12]`	`5`	`22`	items with weights 2 and 3
`[2, 3, 4]`	`[3, 4, 5]`	`5`	`7`	weights 2 and 3
`[1, 2]`	`[10, 20]`	`0`	`0`	no capacity

Going backwards ensures when we compute dp[w], dp[w-weight] still reflects "without this item". Forward iteration would allow reusing.

C++

// Classic 0/1 Knapsack: Given items with weights and values,
// find max value that fits in a knapsack of capacity W.
// Each item can only be used once.
int knapsack01(const std::vector<int>& weights, const std::vector<int>& values, int W) {
    int n = weights.size();
    std::vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

0/1 Knapsack

Why Knapsack State Includes the Item Index