0/1 Knapsack

Choose items with weights and values to maximise value under a capacity. Each cell answers: "best value using the first i items at capacity c?" — take the item or skip it.

Category: Dynamic Programming
Time complexity: O(n·W)
Space complexity: O(n·W)

Pseudocode

row per item, column per capacity
skip: value above
take: value + best without weight
answer at bottom-right

Reference implementation

for i, (w, v) in items:
    for c in range(W + 1):
        dp[i][c] = max(
            dp[i-1][c],
            dp[i-1][c-w] + v if c &gt;= w)

Open the interactive 0/1 Knapsack visualisation →