0/1 knapsack

Choose items to maximize total value within a weight limit. Each item may be used at most once.

Remember: Skip or take once, if it fits.

Example: Values [6,10,12], weights [1,2,3], capacity 5 → value 22.

Time: O(nW). Auxiliary space: O(nW).

Formula: dp[i][c] = max(dp[i−1][c], value[i−1] + dp[i−1][c−weight[i−1]])

Up to 6 nonnegative item values with matching positive integer weights. Capacity 0–8. The take term is allowed only if the item fits. Each item is used at most once. O(nW) is pseudo-polynomial in integer capacity. Compare tabulation with top-down memoization. Both allocate the full table; memoization computes only requested states and adds an O(n) call stack.

Complexities describe the underlying algorithm; tutorial snapshots and rendering can use additional resources.

The interactive workspace loads here when JavaScript is available. You can still browse the learning notes and links above without it.