title: "0/1 Knapsack Problem" description: "Master the 0/1 Knapsack problem DP solution, from recursion to memoization to tabulation." order: 2

0/1 Knapsack Problem

What is 0/1 Knapsack?

The 0/1 Knapsack problem is the most classic DP problem: given N items (each with weight and value), select a subset to put into a knapsack of capacity W to maximize total value. Each item can be taken 0 or 1 time.

| Property | Meaning | |----------|---------| | State | dp[i][w] = max value using first i items, weight <= w | | Recurrence | dp[i][w] = max(skip, take) = max(dp[i-1][w], dp[i-1][w-wi] + vi) | | Base | dp[0][w] = 0, dp[i][0] = 0 | | Time | O(N x W) | | Space | O(N x W) -> can optimize to O(W) |

Implementation

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):
        wi, vi = weights[i-1], values[i-1]
        for w in range(1, capacity + 1):
            if wi <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi)
            else:
                dp[i][w] = dp[i-1][w]

    selected = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            selected.append(i-1)
            w -= weights[i-1]

    return dp[n][capacity], selected

weights = [2, 5, 4, 3, 6]
values = [6, 9, 5, 7, 8]
capacity = 10

max_val, items = knapsack_01(weights, values, capacity)
print(f"Max value: {max_val}")
print(f"Selected items: {items}")

Space Optimized Version

def knapsack_opt(weights, values, capacity):
    """O(W) space, O(NxW) time"""
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        wi, vi = weights[i], values[i]
        for w in range(capacity, wi - 1, -1):
            dp[w] = max(dp[w], dp[w-wi] + vi)
    return dp[capacity]

Summary

| Aspect | Detail | |--------|--------| | State | dp[i][w] = max value with i items, weight <= w | | Recurrence | dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi) | | Base | dp[0][] = 0, dp[][0] = 0 | | Time | O(N x W) | | Space | O(N x W) -> optimized to O(W) | | Backtrack | Reverse trace from dp[n][capacity] |

0/1 Knapsack: Classic DP Application

The 0/1 Knapsack problem is the most classic DP application. Understanding it unlocks DP core concepts - state definition and state transition.

Key to DP Knapsack

State: dp[i][w] = max value using first i items under capacity w
Transition: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
                skip i-th          take i-th (if it fits)

Time Complexity

| Method | Time | Space | When to Use | |--------|------|-------|-------------| | 2D DP | O(nW) | O(nW) | Teaching, easy to understand | | 1D DP (rolling array) | O(nW) | O(W) | Production, memory efficient |

1D Array Optimization

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

Real-World Applications

| Industry | Use | Variant | |----------|-----|--------| | Logistics | Pack containers with boxes to use space | 3D bin packing | | Finance | Build portfolio with budget cap | 0/1 knapsack | | Manufacturing | Cut materials into pieces | Unbounded knapsack | | Cloud Computing | Choose server instances to minimize cost | Multi-dim knapsack | | Retail | Stock shelves with limited space | 2D knapsack | | Marketing | Allocate budget across channels | 0/1 knapsack |

Variant Comparison

| Variant | Item Limit | DP Loop Direction | Space | Time | |---------|-----------|------------------|-------|------| | 0/1 | At most once | Reverse (w from cap to wi) | O(W) | O(nW) | | Unbounded | Any number | Forward (w from wi to cap) | O(W) | O(nW) | | Fractional | Can take part | Greedy by ratio | O(1) | O(n log n) | | Multi-dim | N constraints | 3D+ table | O(W¹W²) | O(nW¹W²) |

Practice Problems

| Problem | Platform | Technique | |---------|----------|----------| | Partition Equal Subset Sum | LeetCode 416 | 0/1, check if sum/2 reachable | | Target Sum | LeetCode 494 | 0/1 with ± assignment | | Coin Change (Fewest) | LeetCode 322 | Unbounded, minimize | | Coin Change 2 (Combos) | LeetCode 518 | Unbounded, count ways | | Ones and Zeroes | LeetCode 474 | 2D knapsack (m x n) | | Shopping Offers | LeetCode 638 | Multi-dimensional | | Last Stone Weight II | LeetCode 1049 | Subset sum | | Profit Maximization | HackerRank | Unbounded knapsack | | Cutting a Rod | GeeksForGeeks | Unbounded (maximize length value) |

Common Mistakes

| Mistake | Fix | |---------|-----| | Forward loop for 0/1 | Iterate capacity from cap down to wi (reverse) | | Reverse loop for unbounded | Iterate capacity from wi up to cap (forward) | | Off-by-one dp array size | Create dp[capacity + 1], not dp[capacity] | | No base case | dp[0] = 0 (zero capacity = zero value) | | Float capacity | Multiply by 10^k to make integer | | Wrong backtrace direction | Start from dp[n][cap], trace backwards | | Forgetting weight 0 items | Handle separately — they break the recurrence |

Summary

The knapsack problem introduces DP optimization. Master the 0/1 variant first, then extend to unbounded and multi-dimensional versions. The recurrence dp[w] = max(dp[w], dp[w-wi] + vi) is the foundation of all knapsack solutions.

Key takeaways:

  • 0/1 knapsack: each item at most once, iterate capacity in reverse
  • Unbounded knapsack: unlimited copies, iterate capacity forward
  • Fractional knapsack: greedy by value/weight ratio (not DP)
  • Space-optimized: 1D array replaces full 2D table (O(W) instead of O(nW))
  • Multi-dimensional: add dimensions for more constraints
  • Backtrace: recover which items were taken from the DP table
  • Practice: subset sum, coin change, partition problems

What's Next: Longest Common Subsequence

The next chapter covers LCS — finding the longest common subsequence between two strings, used in diff tools, DNA alignment, and plagiarism detection.

Time and Space Complexity

| Variant | Time | Space (basic) | Space (optimized) | |---------|------|--------------|------------------| | 0/1 Knapsack | O(n × W) | O(n × W) | O(W) | | Unbounded Knapsack | O(n × W) | O(n × W) | O(W) | | Multi-dimensional | O(n × W¹ × W²) | O(n × W¹ × W²) | O(W¹ × W²) |

Where n = number of items, W = capacity. Note that W is numeric — if W is large (e.g., 10^9), DP becomes impractical and other approaches are needed.

When Knapsack DP Doesn't Work

| Scenario | Alternative | |----------|------------| | W is very large (10^9) | Meet-in-the-middle, branch and bound | | Items have fractional weights | Transform to integers (multiply) | | 3D constraints | Multi-dimensional DP or MILP | | Continuous weights and values | Linear programming | | Real-time decisions | Greedy approximations |

Summary

The knapsack problem is the canonical DP optimization problem. Master the 0/1 recurrence, understand how loop direction changes behavior (reverse for 0/1, forward for unbounded), and practice with real problems.

Key takeaways:

  • 0/1: reverse loop, each item at most once
  • Unbounded: forward loop, unlimited copies
  • Fractional: greedy by value/weight ratio
  • Space-optimized: 1D array, O(W) memory
  • Complexity: O(nW) time, O(W) space optimized
  • Practice: LeetCode 416, 322, 518, 474, 494

Member Exclusive Free Tutorial

This chapter is free exclusive content for registered members! Please login or register to unlock immediately.

Login / Register Now