← all categories

Knapsack 01 ab5927fc

0/1 knapsack (each item used at most once), 1D rolling array. The classic bug: capacity loop must go high-to-low, or an item gets reused within the same iteration (that's the unbounded variant, knapsack-unbounded.h).

Time: O(nW). tested

content/dp/knapsack-01.h

ll knapsack01(vector<ll> &w, vector<ll> &v, ll cap) {
    int n = (int)w.size();
    vector<ll> dp(cap + 1, -1);
    dp[0] = 0;
    for (int i = 0; i < n; i++)
        for (ll j = cap; j >= w[i]; j--)
            if (dp[j - w[i]] != -1) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

    ll ans = 0;
    for (ll j = 0; j <= cap; j++) ans = max(ans, dp[j]);
    return ans;
}