0/1 Knapsack

Dynamic Programming O(n · W) O(n · W)

Maximizes total value under a weight limit, deciding for each item whether to take it or leave it.

i\c	0	1	2	3	4	5
∅	0	·	·	·	·	·
#1	·	·	·	·	·	·
#2	·	·	·	·	·	·
#3	·	·	·	·	·	·

Itemsw1·v6w2·v10w3·v12cap 5

1/25

Base case (no items or no capacity) → dp[0][0] = 0.

Invariantdp[i][c] is the best value using only the first i items within capacity c.

computingreads fromfilled

knapsack.c

int max(int a, int b) { return a > b ? a : b; }
 
int knapsack(int w[], int val[], int n, int W) {
    int dp[n + 1][W + 1];
 
    for (int i = 0; i <= n; i++) {
        for (int c = 0; c <= W; c++) {
            if (i == 0 || c == 0)
                dp[i][c] = 0;
            else if (w[i - 1] > c)
                dp[i][c] = dp[i - 1][c];
            else
                dp[i][c] = max(dp[i - 1][c],
                    dp[i - 1][c - w[i - 1]] + val[i - 1]);
        }
    }
    return dp[n][W];
}

How 0/1 Knapsack works

For each item and each capacity, keep the best of two worlds: skip the item, or take it and add its value to the best result for the remaining capacity. The table reuses every sub-answer.

When to use it

Budgeted selection problems where items are indivisible: cargo, project portfolios, cutting stock.