0/1 Knapsack Algorithm Tutorial

The $0/1$ Knapsack problem asks: given $n$ items, each with a weight and value, what's the maximum value you can carry in a bag with capacity $W$?

The "$0/1$" means you either take an item completely or leave it behind. No splitting allowed. You can't take half a laptop.

Example: You have $3$ items:

• Item A: weight $2$, value $3$
• Item B: weight $3$, value $4$
• Item C: weight $4$, value $5$

With capacity $5$, your best choice is items A + B for total value $7$.

Real applications: budget allocation across projects, loading cargo onto trucks, selecting features under time constraints.

For each item, you face a binary decision: take it or skip it.

If you take item $i$:

• Your remaining capacity drops by its weight
• You gain its value
• You move to the next item

If you skip item $i$:

• Capacity stays the same
• You gain nothing from this item
• You move to the next item

You want the combination that maximizes total value without exceeding capacity $W$.

Think of it recursively. At each step, you compare: "What's better? Taking this item (if it fits) or skipping it?" The answer depends on what you can do with the remaining items and remaining capacity.

You define $dp[i][w]$ as the maximum value achievable using the first $i$ items with capacity $w$.

Base case: $dp[0][w] = 0$ for all $w$. With zero items, you get zero value.

Transition: For each item $i$ with weight $wt[i]$ and value $val[i]$:

$dp[i][w] = \max(dp[i-1][w], \quad dp[i-1][w - wt[i]] + val[i])$

The first term is skipping item $i$. The second term is taking it (only valid when $w \geq wt[i]$).

You build the table row by row. Each cell asks: "Given this capacity and these items available, what's the best I can do?" The answer at $dp[n][W]$ gives your final result.

Here's the complete $2$D dynamic programming solution:

function knapsack(weights, values, W):
    n = length(weights)
    dp = 2D array of size (n+1) x (W+1), initialized to 0
    
    for i from 1 to n:
        for w from 0 to W:
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]

Reconstructing the solution: Start at $dp[n][W]$. If $dp[i][w] \neq dp[i-1][w]$, item $i$ was taken. Move to $dp[i-1][w - weights[i-1]]$. Otherwise, move to $dp[i-1][w]$. Repeat until $i = 0$.