Knapsack DP

Knapsack DP covers optimization and counting on a capacity with items having weight (and often value). The 0/1 version uses each item once; the unbounded version repeats items.

0/1 knapsack (maximize value)

dp[w] = maximum value achievable with total weight at most w. Process each item once; iterate w downwards so each item is used at most once.

#include <vector>
#include <algorithm>
using namespace std;

int knapsack01(const vector<int>& weight, const vector<int>& value, int W) {
    vector<int> dp(W + 1, 0);
    int n = (int)weight.size();
    for (int i = 0; i < n; i++)
        for (int w = W; w >= weight[i]; w--)
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
    return dp[W];
}

Unbounded knapsack

Same as 0/1 but iterate w forwards (or inner loop ascending) so the same item can be taken again.

int knapsackUnbounded(const vector<int>& weight, const vector<int>& value, int W) {
    vector<int> dp(W + 1, 0);
    int n = (int)weight.size();
    for (int i = 0; i < n; i++)
        for (int w = weight[i]; w <= W; w++)
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
    return dp[W];
}

Counting ways / subset sums

• Subset sum (boolean): whether some subset sums to T — dp as vector<bool> or bitset.
• Number of subsets with given sum — use dp[w] as count and add contributions.

Complexity

• Time: \(O(n \cdot W)\) for \(n\) items and capacity \(W\).
• Space: \(O(W)\) with rolling one-dimensional array; \(O(n \cdot W)\) if you need to reconstruct the solution.

Related

• Coin Change — same recurrence ideas on “amount” instead of explicit items
• Bitmask DP — when \(n\) is small and state is a subset of items