Dynamic Programming: The 0/1 Knapsack Problem

The 0/1 Knapsack Problem is a classic combinatorial optimization problem. Given $N$ items, each with a specific weight $w_i$ and value $v_i$, and a knapsack with maximum weight capacity $W$, determine the maximum total value of items that can fit in the knapsack.

Unlike the fractional knapsack problem (which can be solved greedily), 0/1 Knapsack requires Dynamic Programming (DP) because items cannot be broken into fractions.

1. Summary & Key Takeaways

• Sub-Problem Recurrence Relation: $DP[i][w] = \max\left(DP[i-1][w], \, v_i + DP[i-1][w - w_i]\right)$
• State Definition: $DP[i][w]$ represents the maximum value achievable considering the first $i$ items with capacity $w$.
• Time Complexity: $O(N \cdot W)$ pseudo-polynomial time (where $N$ is item count and $W$ is capacity).
• Space Complexity: $O(N \cdot W)$ using a full 2D table, or $O(W)$ space using 1D space optimization.

2. Interactive Knapsack Playground

Use the interactive memoization matrix below to step through sub-problem evaluations cell-by-cell!

# 0/1 Knapsack Dynamic Programming in Python

def knapsack(W, weights, values):
    n = len(values)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][W]

3. Formulated Memoization Matrix Solution

For the sample catalog below ($W = 7$):

• Gemstone: Weight $= 2$, Value =\3$
• Gold Bar: Weight $= 3$, Value =\4$
• Artifact: Weight $= 4$, Value =\5$
• Crown: Weight $= 5$, Value =\8$

Here is the completed $DP[i][w]$ state matrix:

At capacity $W=7$, the optimal combination takes the Crown (W=5, V=\8$) + **Gemstone** ($W=2, V=$3$) for a maximum profit of **$$11$**!

4. Knapsack Variants Matrix