0/1 Knapsack Problem

Analogy categoryAnalogies

Introduction

The 0/1 knapsack problem asks: given n items, each with a weight and a value, and a knapsack with maximum weight capacity W, choose a subset of items to maximize total value without exceeding W. Each item can be taken at most once (hence '0/1' — take it or leave it), which distinguishes it from the fractional knapsack problem where items can be split. This problem has optimal substructure (the best solution for capacity W using the first i items depends on optimal solutions using fewer items or less capacity) and overlapping subproblems (the same (item index, remaining capacity) pair recurs across many decision paths), making it a textbook DP problem.

🏏

Cricket analogy: Picking your XI for a T20 final is a 0/1 knapsack: each player has a 'weight' (salary cap) and a 'value' (expected impact), and you either pick MS Dhoni or you don't — you can't take half of him to save cap space, unlike the fractional version.

Approach/Syntax

python

# dp[i][w] = maximum value achievable using the first i items with capacity w
# Recurrence:
#   dp[0][w] = 0 for all w                      (no items -> no value)
#   dp[i][w] = dp[i-1][w]                        if weight[i-1] > w (can't fit item i-1)
#   dp[i][w] = max(dp[i-1][w],
#                  dp[i-1][w - weight[i-1]] + value[i-1])   otherwise

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

    for i in range(1, n + 1):
        w_i, v_i = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]  # option 1: skip item i-1
            if w_i <= w:
                take = dp[i - 1][w - w_i] + v_i  # option 2: take item i-1
                if take > dp[i][w]:
                    dp[i][w] = take
    return dp

Explanation

dp[i][w] represents the best value obtainable using only the first i items with a capacity budget of w. For each item, there are exactly two choices: skip it (value stays dp[i-1][w]) or take it, which is only possible if its weight fits (w_i <= w), yielding dp[i-1][w - w_i] + v_i. Taking the max of these two options at every cell guarantees optimal substructure is respected. Because dp[i-1][*] is reused across many different w values and across the decision to take or skip later items, the same subproblems overlap heavily — exactly the pattern DP is built to exploit.

🏏

Cricket analogy: A selector's table dp[i][w] tracks the best team score using only the first i shortlisted players within a wage budget w; for each player the choice is drop them (score stays the same) or field them if their wage fits, reusing the same budget rows across many player lists.

Example

code

def knapsack_01_with_items(weights, values, capacity):
    n = len(weights)
    dp = knapsack_01(weights, values, capacity)

    # Reconstruct chosen items by walking the table backward
    chosen = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:  # item i-1 was taken
            chosen.append(i - 1)
            w -= weights[i - 1]
    chosen.reverse()
    return dp[n][capacity], chosen

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5

best_value, items_taken = knapsack_01_with_items(weights, values, capacity)
print(f"Best value: {best_value}")          # Best value: 7
print(f"Items taken (indices): {items_taken}")  # Items taken (indices): [0, 1]

Output/Complexity

For weights=[2,3,4,5], values=[3,4,5,6], capacity=5, the optimal choice is items 0 and 1 (weight 2+3=5, value 3+4=7), so the output is 'Best value: 7' and 'Items taken (indices): [0, 1]'. The algorithm fills an (n+1) x (W+1) table, so both time and space complexity are O(n * W), where n is the number of items and W is the capacity. This is pseudo-polynomial because it depends on the numeric value of W, not just the number of items; the space can be reduced to O(W) by iterating the weight dimension from high to low using a single 1D array, though the two-item-per-cell version shown here is clearer for learning and item reconstruction.

🏏

Cricket analogy: With four all-rounders of weights 2,3,4,5 and impact scores 3,4,5,6 under a squad weight cap of 5, picking players 0 and 1 gives the max impact score of 7, filling a table sized by (players+1) x (cap+1), an O(n*W) pseudo-polynomial exercise.

Key Takeaways

0/1 knapsack means each item is either fully taken or fully left out — no fractional items.
The recurrence dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + value[i-1]) captures the skip-or-take decision.
Time and space complexity are both O(n * W), which is pseudo-polynomial in the capacity W.
The chosen items can be reconstructed by walking the filled table backward and comparing dp[i][w] to dp[i-1][w].
Space can be optimized to O(W) using a 1D array updated from high capacity to low capacity.

Practice what you learned

1. What distinguishes the 0/1 knapsack problem from the fractional knapsack problem?

2. What is the time complexity of the standard 0/1 knapsack DP solution with n items and capacity W?

3. In the recurrence dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + value[i-1]), what does the first term dp[i-1][w] represent?

4. How can the chosen items be reconstructed after filling the DP table?

Was this page helpful?

Memoization vs Tabulation

Longest Common Subsequence

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#01KnapsackProblem#Knapsack#Problem#Approach#Syntax#StudyNotes#SkillVeris