0/1 Knapsack · Algorithms (DAA)

You have n items, each with a weight and a value, and a knapsack of capacity W. Each item is taken whole or not at all (0 or 1). Maximise the total value without exceeding W.

Greedy by value-per-weight fails here (see the greedy lesson); trying all 2ⁿ subsets is too slow. DP solves it in O(nW).

State and recurrence

State: dp[i][w] = the best value achievable using the first i items with capacity w.

For item i (weight wᵢ, value vᵢ), either skip it or take it (if it fits):

dp[i][w] = dp[i−1][w] if wᵢ > w dp[i][w] = max(dp[i−1][w], vᵢ + dp[i−1][w − wᵢ]) otherwise

Base: dp[0][w] = 0 (no items) and dp[i][0] = 0 (no capacity). Answer: dp[n][W].

Watch the table fill

Code with traceback

C++

#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
using namespace std;

int main() {
    vector<string> name = {"", "A", "B", "C", "D"};
    vector<int> wt = {0, 1, 3, 4, 5}, val = {0, 1, 4, 5, 7};
    int n = 4, W = 7;
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i - 1][w];                                    // skip item i
            if (wt[i] <= w) dp[i][w] = max(dp[i][w], val[i] + dp[i - 1][w - wt[i]]);   // or take it
        }

    cout << "item\\w";
    for (int w = 0; w <= W; w++) cout << setw(3) << w;
    cout << endl;
    for (int i = 0; i <= n; i++) {
        cout << setw(6) << (i ? name[i] + "(" + to_string(wt[i]) + "," + to_string(val[i]) + ")" : "-");
        for (int w = 0; w <= W; w++) cout << setw(3) << dp[i][w];
        cout << endl;
    }

    cout << "best value = " << dp[n][W] << ", items:";
    for (int i = n, w = W; i > 0; i--)
        if (dp[i][w] != dp[i - 1][w]) { cout << " " << name[i]; w -= wt[i]; }   // value changed: i was taken
    cout << endl;
    return 0;
}

Output

item\w  0  1  2  3  4  5  6  7
     -  0  0  0  0  0  0  0  0
A(1,1)  0  1  1  1  1  1  1  1
B(3,4)  0  1  1  4  5  5  5  5
C(4,5)  0  1  1  4  5  6  6  9
D(5,7)  0  1  1  4  5  7  8  9
best value = 9, items: C B

Try it Yourself

Traceback: start at dp[n][W]. If the value equals the cell above, item i was skipped; otherwise it was taken — subtract its weight and move up.

Space optimisation

Each row depends only on the previous row, so one 1-D array suffices if you loop w downwards (so each item is used at most once):

C++

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

int main() {
    vector<int> wt = {1, 3, 4, 5}, val = {1, 4, 5, 7};
    int W = 7;
    vector<int> dp(W + 1, 0);
    for (size_t i = 0; i < wt.size(); i++)
        for (int w = W; w >= wt[i]; w--)                 // downwards!
            dp[w] = max(dp[w], val[i] + dp[w - wt[i]]);
    cout << "best value = " << dp[W] << endl;
    return 0;
}

Output

best value = 9

Try it Yourself

Looping w upwards would allow an item to be reused — which solves the unbounded knapsack instead.

Test yourself

4 questions · pick an answer to check it instantly

1
In 0/1 knapsack, what does dp[i][w] represent?
2
If wt[i] > w, what is dp[i][w]?
3
Items (w, v): (1, 1), (3, 4), (4, 5), (5, 7); W = 7. What is the maximum value?
4
In the 1-D version, why loop w from W down to wt[i]?

#State and recurrence

#Watch the table fill

#Code with traceback

#Space optimisation

Test yourself

State and recurrence

Watch the table fill

Code with traceback

Space optimisation