0/1 Knapsack (Dynamic Programming)

The problem

A thief has a bag that can carry at most W kg. There are n items, each with a weight w[i] and a value v[i]. Each item can be taken whole or not at all — that’s the “0/1”. Which items maximise the total value without breaking the bag?

Trying every subset means 2ⁿ possibilities — about a million for 20 items and a trillion for 40. Dynamic programming solves it in O(n × W).

Dynamic programming in one sentence

Solve small versions of the problem first, store their answers in a table, and build bigger answers from smaller ones.

Here, the small version is: “What is the best value using only the first i items, with a bag of capacity c?” We call that dp[i][c].

The recurrence: skip or take

For item i and capacity c there are only two choices:

• Skip it → the value is dp[i−1][c] (best without this item).
• Take it (only if w[i] ≤ c) → v[i] + dp[i−1][c − w[i]] (its value plus the best we can do with the remaining capacity).

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

Base case: dp[0][c] = 0 (no items) and dp[i][0] = 0 (no capacity).

In the 3D model each cell is a bar whose height is its value. When a cell is computed, the cell directly above (skip, yellow) and the cell above-left by w[i] (take, purple) light up.

Tracing back the chosen items

The answer is dp[n][W]. To find which items were taken, start at the bottom-right cell and walk up: if dp[i][c] ≠ dp[i−1][c], item i was taken, so subtract its weight from c. The model highlights this path in green.

Code

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(W + 1):
            dp[i][c] = dp[i - 1][c]                        # skip
            if w <= c:
                dp[i][c] = max(dp[i][c], v + dp[i - 1][c - w])   # take
    # trace back
    chosen, c = [], W
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i - 1][c]:
            chosen.append(i)
            c -= weights[i - 1]
    return dp[n][W], chosen[::-1]

print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))   # (9, [2, 3])

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

int main() {
    vector<int> w = {1, 3, 4, 5}, v = {1, 4, 5, 7};
    int n = w.size(), W = 7;
    // Space-saving version: one row, filled from right to left.
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++)
        for (int c = W; c >= w[i]; c--)
            dp[c] = max(dp[c], v[i] + dp[c - w[i]]);
    cout << dp[W] << "\n";   // 9
}

The C++ version uses a single row of size W + 1. Going right to left makes sure each item is used at most once — a classic interview follow-up.

0/1 vs fractional knapsack

	0/1 knapsack	Fractional knapsack
Items	Whole or nothing	Can take a fraction
Best method	Dynamic programming, O(nW)	Greedy by value/weight ratio, O(n log n)

The DP recipe (works for many problems)

1. Define the state: what does dp[i][c] mean?
2. Find the recurrence: how does a state depend on smaller states?
3. Set base cases.
4. Fill the table in the right order.
5. Read the answer (and trace back if you need the choices).

The same recipe solves Longest Common Subsequence, coin change, edit distance and many more.

Common mistakes

• Iterating capacity left-to-right in the 1-row version (lets an item be used twice — that’s the unbounded knapsack).
• Off-by-one errors between item numbers (1-based in the table) and list indexes (0-based).
• Forgetting the “doesn’t fit” case.