0/1 Knapsack

O(n·W)

Given items with weights and values and a total weight capacity, 0/1 knapsack chooses a subset of maximum value that still fits — each item is taken entirely or left behind (no fractions). The DP table dp[i][w] holds the best value using the first i items within capacity w. Each cell is the better of two choices: skip item i (copy the value from the row above) or take it (its value plus the best for the remaining capacity w − weight, from the row above). Filling the table is O(n·W); the bottom-right cell is the optimum. It models budgeting, cargo loading, and resource allocation, and — like subset sum — it's NP-hard but solved pseudo-polynomially here.

DP table
Press ▶ to run
Edit the input and press Play

How it works

  1. With no items, every capacity holds value 0 — the base row.
  2. For each item and capacity, first copy the best value that skips this item (the row above).
  3. If the item fits, compare with its value plus the best for the leftover capacity.
  4. Keep the larger; the bottom-right cell is the most valuable load.

Pseudocode

1knapsack(weights, values, W):       # O(n·W)2  dp[0][w] ← 0                       # no items → no value3  for each item i, capacity w in 1..W:4    best ← dp[i-1][w]                # skip item i5    if w ≥ weight[i]:6      take ← dp[i-1][w-weight[i]] + value[i]7      best ← max(best, take)         # take item i8    dp[i][w] ← best9  return dp[n][W]