How to Solve Knapsack Problems (0-1, Unbounded, Subset) Using Dynamic Programming

You solve knapsack problems by defining a DP state dp[i][w] representing the maximum value achievable using the first i items with capacity w, then applying recurrence relations that either exclude the item or include it (once for 0-1 knapsack, unlimited times for unbounded knapsack), achieving optimal O(N·W) time complexity with O(W) space optimization.

The repository labuladong/fucking-algorithm provides authoritative dynamic programming solutions for classic knapsack variants in its Dynamic Programming series. The framework centers on systematic state transition logic that distinguishes between constrained single-use scenarios and flexible multi-use configurations, enabling you to maximize value within any weight capacity.

Understanding the 0-1 Knapsack Problem

According to 动态规划系列/背包问题.md, the 0-1 knapsack restricts each item to at most one selection. This constraint fundamentally shapes the state transition logic and iteration pattern required for correct computation.

State Definition and Transition

The solution defines dp[i][w] as the maximum value obtainable by selecting from the first i items without exceeding capacity w. The reference Java implementation (lines 44-63) establishes the recurrence by evaluating two exclusive choices for each item:

• Exclude item i: Carry forward the previous optimal value dp[i-1][w]
• Include item i (only if w ≥ wt[i-1]): Add val[i-1] to the optimal subproblem solution dp[i-1][w-wt[i-1]]

This yields the transition equation:

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

Space Optimization to O(W)

Because each state depends exclusively on the previous row (i-1), we compress the 2D DP table into a 1D array of size W+1. The critical implementation detail requires iterating backwards through the capacity dimension:

for i in range(N):
    for w in range(W, wt[i] - 1, -1):  # Decreasing order

        dp[w] = max(dp[w], dp[w - wt[i]] + val[i])

This backward traversal prevents overwriting dp[w-wt[i]] with the current item's value before it is used to compute dp[w], ensuring each item is counted at most once.

Solving the Unbounded (Complete) Knapsack Problem

For the unbounded knapsack—where each item may be selected an unlimited number of times—the repository references the external article linked in 动态规划系列/状态压缩技巧.md (line 198). While the state definition remains conceptually similar, the transition logic modifies to allow repeated selection of the same item.

Modified State Transition

The recurrence shifts to a 1D formulation where dp[w] represents the maximum value for capacity w considering all items up to the current index:

dp[w] = max(dp[w], dp[w-wt[i]] + val[i]) for all w ≥ wt[i]

Unlike the 0-1 version, the term dp[w-wt[i]] on the right-hand side may already include the current item i, effectively permitting unlimited reuse.

Implementation Differences

The traversal direction reverses to forwards iteration:

for i in range(N):
    for w in range(wt[i], W + 1):  # Increasing order

        dp[w] = max(dp[w], dp[w - wt[i]] + val[i])

This forward pass ensures that when computing dp[w], the subproblem dp[w-wt[i]] potentially contains the current item's value, enabling the accumulation of multiple copies.

Algorithm Comparison and Complexity Analysis

Both variants achieve identical asymptotic complexity but require distinct iteration patterns:

• 0-1 Knapsack: O(N·W) time and O(W) space. Iterate items outer loop, capacity decreasing inner loop. Each item processed exactly once per capacity.
• Unbounded Knapsack: O(N·W) time and O(W) space. Iterate items outer loop, capacity increasing inner loop. Allows accumulation of multiple item copies.

Complete Python Implementations

The following implementations demonstrate the practical application of these DP principles:

# 0-1 knapsack: each item used at most once

def knapsack_01(W, wt, val):
    N = len(wt)
    dp = [0] * (W + 1)
    for i in range(N):
        # Traverse backwards to prevent reuse

        for w in range(W, wt[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]

# Unbounded knapsack: unlimited item copies

def knapsack_unbounded(W, wt, val):
    N = len(wt)
    dp = [0] * (W + 1)
    for i in range(N):
        # Traverse forwards to enable reuse

        for w in range(wt[i], W + 1):
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]

# Example execution

if __name__ == "__main__":
    W = 4
    wt = [2, 1, 3]
    val = [4, 2, 3]
    
    print("0-1 knapsack:", knapsack_01(W, wt, val))           # Output: 6

    print("Unbounded knapsack:", knapsack_unbounded(W, wt, val)) # Output: 8

Summary

• State definition: Use dp[i][w] (or compressed dp[w]) to track maximum value for first i items and capacity w.
• 0-1 transition: max(dp[i-1][w], dp[i-1][w-wt[i-1]] + val[i-1]) with backwards capacity iteration.
• Unbounded transition: max(dp[w], dp[w-wt[i]] + val[i]) with forwards capacity iteration.
• Space optimization: Both approaches reduce from O(N·W) to O(W) by using 1D arrays with appropriate traversal directions.
• Source reference: Implementation details are documented in 动态规划系列/背包问题.md and linked resources within labuladong/fucking-algorithm.

Frequently Asked Questions

What is the fundamental difference between 0-1 and unbounded knapsack?

The 0-1 knapsack restricts each item to zero or one use, requiring you to choose between including or excluding each item exactly once. The unbounded knapsack permits unlimited copies of each item, transforming the decision from a binary choice into a quantity optimization problem where you can repeatedly select profitable items.

Why must we iterate backwards for 0-1 knapsack but forwards for unbounded knapsack?

In the 0-1 knapsack, backwards iteration ensures that dp[w-wt[i]] refers to the state from the previous item iteration (i-1), preventing the current item from being counted multiple times in the same solution. For unbounded knapsack, forwards iteration allows dp[w-wt[i]] to potentially contain the current item already, enabling the accumulation of unlimited copies as you progress through increasing capacities.

Can the subset sum problem be solved using this knapsack framework?

Yes, the subset sum problem is a special case of the 0-1 knapsack where val[i] = wt[i] and the goal is to determine if capacity W can be filled exactly. You modify the DP to track boolean feasibility (dp[w] = dp[w] or dp[w-wt[i]]) rather than maximizing value, utilizing the same state transition logic described in 动态规划系列/背包问题.md.

How does the space optimization from 2D to 1D DP maintain correctness?

The 2D array dp[i][w] only depends on row i-1, never on earlier rows. By overwriting a single 1D array dp[w] in-place, we preserve the necessary previous state values if we traverse in the correct order: backwards for 0-1 (preserving the i-1 state for smaller capacities) and forwards for unbounded (allowing the updated state to influence larger capacities immediately).

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}