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

> Master knapsack problems like 0-1, unbounded, and subset using dynamic programming. Learn optimal O(N·W) time and O(W) space solutions. Explore the DP state and recurrence relations used.

- Repository: [DonglaiFu/fucking-algorithm](https://github.com/labuladong/fucking-algorithm)
- Tags: tutorial
- Published: 2026-02-25

---

**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:

```python
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:

```python
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:

```python

# 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).