Knapsack Problem: 0/1 and Unbounded Variants

Key Insights

The 0/1 knapsack uses reverse iteration in its space-optimized form to prevent using the same item twice, while unbounded knapsack uses forward iteration to allow unlimited item reuse.
Both variants share O(nW) time complexity, but the 2D solution provides item reconstruction capability that the 1D optimization sacrifices.
Recognizing which variant applies to your problem—and the related problems like subset sum and coin change—is more valuable than memorizing solutions.

Introduction to the Knapsack Problem

You have a backpack with limited capacity. You’re staring at a pile of items, each with a weight and a value. Which items do you take to maximize value without exceeding capacity?

This deceptively simple question underlies countless real-world optimization problems. Cloud providers use knapsack algorithms to allocate virtual machines across physical hosts. Investment firms optimize portfolio allocation under budget constraints. Shipping companies maximize cargo value within weight limits. Even Netflix uses variants when deciding which content to cache on edge servers given storage constraints.

The knapsack problem appears frequently in technical interviews because it elegantly tests dynamic programming intuition. More importantly, understanding it deeply unlocks a family of related problems: subset sum, partition problems, and coin change. Master knapsack, and you’ve mastered a pattern that applies to dozens of interview questions.

Let’s build that mastery.

0/1 Knapsack: Problem Definition

In the 0/1 variant, each item is a binary choice: take it or leave it. You cannot take fractional items or multiple copies. Given n items and a knapsack capacity W, select items to maximize total value without exceeding total weight.

Formally:

Input: Array of items (each with weight and value), capacity W
Output: Maximum achievable value, optionally the selected items
Constraint: Each item used at most once

from dataclasses import dataclass
from typing import List, Tuple

@dataclass
class Item:
    name: str
    weight: int
    value: int

def create_sample_items() -> List[Item]:
    return [
        Item("laptop", 3, 4),
        Item("camera", 1, 1),
        Item("headphones", 2, 3),
        Item("book", 2, 1),
        Item("tablet", 4, 5),
    ]

The “0/1” name reflects the binary nature: each item’s selection is either 0 (excluded) or 1 (included).

0/1 Knapsack: Dynamic Programming Solution

The brute force approach considers all 2^n subsets—exponential and impractical. Dynamic programming reduces this by recognizing overlapping subproblems.

Define dp[i][w] as the maximum value achievable using the first i items with capacity w. For each item, we make a choice:

Skip it: dp[i][w] = dp[i-1][w]
Take it (if it fits): dp[i][w] = dp[i-1][w - weight[i]] + value[i]

We take the maximum of both options. This builds a 2D table where each cell depends only on the row above it.

def knapsack_01(items: List[Item], capacity: int) -> int:
    n = len(items)
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        item = items[i - 1]
        for w in range(capacity + 1):
            # Option 1: don't take item i
            dp[i][w] = dp[i - 1][w]
            
            # Option 2: take item i (if it fits)
            if item.weight <= w:
                take_value = dp[i - 1][w - item.weight] + item.value
                dp[i][w] = max(dp[i][w], take_value)
    
    return dp[n][capacity]

Time complexity: O(nW) — we fill n×W cells, each in O(1). Space complexity: O(nW) — the full table.

Note that this is pseudo-polynomial: it’s polynomial in the numeric value of W, not in the input size. If W is encoded in binary (log W bits), the algorithm is exponential in input size. This distinction matters for theoretical analysis but rarely affects practical use.

Reconstructing the Solution

The table tells us the maximum value, but which items achieved it? Backtrack from dp[n][capacity]:

def knapsack_01_with_items(items: List[Item], capacity: int) -> Tuple[int, List[Item]]:
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        item = items[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]
            if item.weight <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - item.weight] + item.value)
    
    # Backtrack to find selected items
    selected = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            # Item i was taken
            selected.append(items[i - 1])
            w -= items[i - 1].weight
    
    return dp[n][capacity], selected

# Usage
items = create_sample_items()
max_value, selected = knapsack_01_with_items(items, 6)
print(f"Max value: {max_value}")  # Max value: 8
print(f"Selected: {[item.name for item in selected]}")  # Selected: ['tablet', 'headphones']

The backtracking logic is straightforward: if the value changed between rows, we took that item.

0/1 Knapsack: Space Optimization

Since each row depends only on the previous row, we can reduce space to O(W) using a single array. The critical insight: iterate capacity in reverse.

Why reverse? When computing dp[w], we need dp[w - weight] from the previous iteration. Forward iteration would overwrite dp[w - weight] before we use it, effectively allowing the same item to be used multiple times.

def knapsack_01_optimized(items: List[Item], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    
    for item in items:
        # Iterate backwards to prevent using same item twice
        for w in range(capacity, item.weight - 1, -1):
            dp[w] = max(dp[w], dp[w - item.weight] + item.value)
    
    return dp[capacity]

This is elegant and memory-efficient, but you lose the ability to reconstruct which items were selected. If you need the items, stick with the 2D approach or implement a separate backtracking pass with the 2D table.

Unbounded Knapsack: Problem Definition & Solution

The unbounded variant removes the “once only” constraint. Each item has unlimited copies available. Think of it as a vending machine: you can buy as many of each item as you can afford.

This changes the recurrence subtly but significantly. Instead of looking at the previous row (previous item), we look at the current row (same item still available):

def knapsack_unbounded(items: List[Item], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    
    for item in items:
        # Iterate forwards - allows reusing the same item
        for w in range(item.weight, capacity + 1):
            dp[w] = max(dp[w], dp[w - item.weight] + item.value)
    
    return dp[capacity]

The only difference from the space-optimized 0/1 solution is the iteration direction. Forward iteration means when we compute dp[w], dp[w - weight] already reflects the current item—allowing unlimited reuse.

Alternatively, structure it like coin change for clarity:

def knapsack_unbounded_explicit(items: List[Item], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    
    for w in range(1, capacity + 1):
        for item in items:
            if item.weight <= w:
                dp[w] = max(dp[w], dp[w - item.weight] + item.value)
    
    return dp[capacity]

Both approaches yield identical results with O(nW) time and O(W) space.

Comparison and Variant Selection Guide

Choosing the right variant comes down to one question: Can items be reused?

Scenario	Variant	Example
Physical items	0/1	Packing a suitcase
Unlimited supply	Unbounded	Buying stocks, cutting rods
Limited quantities	Bounded (extension)	Inventory with stock counts

Performance Considerations & Edge Cases

Large Capacities

When W is enormous but n is small (say, n ≤ 40), the standard DP becomes impractical. The meet-in-the-middle approach splits items into two halves, enumerates all 2^(n/2) subsets for each, and combines results. This reduces complexity to O(2^(n/2) × n), feasible for n up to 40.

Common Pitfalls

Off-by-one errors: Arrays are 0-indexed, but the DP table often uses 1-indexing for items
Integer overflow: Large values can overflow; use appropriate types
Forgetting the empty case: Always handle zero items or zero capacity

def test_knapsack_edge_cases():
    # Empty items
    assert knapsack_01([], 10) == 0
    
    # Zero capacity
    items = [Item("test", 5, 10)]
    assert knapsack_01(items, 0) == 0
    
    # Single item that fits
    assert knapsack_01(items, 5) == 10
    
    # Single item that doesn't fit
    assert knapsack_01(items, 4) == 0
    
    # All items fit
    items = [Item("a", 1, 1), Item("b", 1, 2)]
    assert knapsack_01(items, 10) == 3
    
    # Item weight equals capacity exactly
    items = [Item("exact", 5, 100)]
    assert knapsack_01(items, 5) == 100
    
    # Unbounded: verify item reuse
    items = [Item("coin", 2, 3)]
    assert knapsack_unbounded(items, 6) == 9  # Take 3 copies
    
    print("All edge case tests passed!")

test_knapsack_edge_cases()

Debugging Tips

When your solution fails:

Print the DP table for small inputs
Verify base cases (row 0 and column 0 should be zeros)
Check iteration direction matches your variant
Trace through one item manually

The knapsack problem rewards understanding over memorization. Know why reverse iteration prevents reuse, and you’ll never confuse the variants again. Know how to backtrack through the table, and you can adapt to any “find the actual items” follow-up. These fundamentals transfer to the entire family of subset and partition problems you’ll encounter.