# Key Patterns in Knapsack-Related Dynamic Programming Problems: 0-1, Complete, and Multiple Variants Explained

> Master knapsack DP with 0-1, complete, and multiple variants. Learn state transitions, initialization, and traversal orders to solve these common dynamic programming problems.

- Repository: [程序员Carl/leetcode-master](https://github.com/youngyangyang04/leetcode-master)
- Tags: deep-dive
- Published: 2026-03-05

---

**The `leetcode-master` repository by youngyangyang04 structures knapsack DP around three core variants—0-1, complete, and multiple knapsack—with distinct state transitions, initialization rules, and traversal orders that determine whether items can be reused.**

The repository provides a comprehensive analysis of knapsack patterns across files like `problems/背包理论基础01背包-2.md` and `problems/背包问题完全背包一维.md`, demonstrating how to derive solutions from first principles. These implementations reveal that the difference between 0-1 and complete knapsack problems lies primarily in the transition equation and the direction of the capacity iteration, not just the problem constraints.

## State Definitions and Transition Equations

All knapsack variants in the repository follow a consistent state definition: **dp[i][j]** represents the maximum value achievable using the first `i` items with a total weight not exceeding `j`.

The critical divergence appears in the transition logic:

- **0-1 Knapsack** (`problems/背包理论基础01背包-2.md`): Each item can be used at most once. The recurrence references the previous row to ensure no reuse:

  ```

  dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
  ```

- **Complete Knapsack** (`problems/背包问题理论基础完全背包.md`): Items can be used unlimited times. The recurrence stays in the current row because the current item may be reused:

  ```

  dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])
  ```

- **Multiple Knapsack** (`problems/背包理论基础多重背包.md`): Each item has a limited count `cnt[i]`. The repository recommends splitting bounded items into multiple 0-1 items or using a nested loop `for k in 1..cnt[i]` with capacity traversing downwards.

## Space Optimization: 2D to 1D Arrays

The repository emphasizes compressing the 2-D `dp[N][W+1]` matrix into a 1-D rolling array `dp[W+1]` to reduce space complexity from **O(NW)** to **O(W)**.

### 0-1 Knapsack with Descending Capacity

When using a 1-D array for 0-1 knapsack, the code in `problems/背包理论基础01背包-2.md` mandates iterating capacity **descending** from `W` down to `w[i]`. This prevents the same item from being counted multiple times in a single iteration.

```cpp
vector<int> dp(W + 1, 0);
for (int i = 0; i < N; ++i) {
    for (int j = W; j >= w[i]; --j) {          // descending order critical
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

```

### Complete Knapsack with Flexible Traversal

For complete knapsack problems, the repository demonstrates in `problems/背包问题完全背包一维.md` that traversal order becomes flexible. Because the transition `dp[i][j-w[i]]` references the current row (allowing reuse), both "item-outer" and "capacity-outer" loops produce correct results.

```cpp
vector<int> dp(W + 1, 0);
for (int i = 0; i < N; ++i) {
    for (int j = w[i]; j <= W; ++j) {          // ascending order works
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

```

## Initialization Strategies

The initialization phase varies by variant to handle base cases correctly:

- **0-1 Knapsack**: Initialize `dp[0][j] = 0` for all `j`, representing zero value with zero items.
- **Complete Knapsack**: Initialize the first row with `dp[0][j] = (j / w[0]) * v[0]` for `j >= w[0]`, accounting for unlimited copies of the first item.
- **Multiple Knapsack**: After splitting items, follow the 0-1 initialization pattern.

## Implementation Examples

Below are production-ready implementations extracted from the repository's documentation files.

### C++ 0-1 Knapsack (Rolling Array)

Source: `problems/背包理论基础01背包-2.md`

```cpp
int main() {
    int N, W;
    cin >> N >> W;
    vector<int> w(N), v(N);
    for (int i = 0; i < N; ++i) cin >> w[i] >> v[i];

    vector<int> dp(W + 1, 0);
    for (int i = 0; i < N; ++i) {
        for (int j = W; j >= w[i]; --j) {          // descending capacity
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]); // skip vs take
        }
    }
    cout << dp[W] << endl;
}

```

### C++ Complete Knapsack (1-D DP)

Source: `problems/背包问题完全背包一维.md`

```cpp
int main() {
    int N, W;
    cin >> N >> W;
    vector<int> w(N), v(N);
    for (int i = 0; i < N; ++i) cin >> w[i] >> v[i];

    vector<int> dp(W + 1, 0);
    // either item-outer or capacity-outer works; shown item-outer
    for (int i = 0; i < N; ++i) {
        for (int j = w[i]; j <= W; ++j) {          // forward capacity
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]); // unlimited reuse
        }
    }
    cout << dp[W] << endl;
}

```

### Python Complete Knapsack (Functional Style)

Source: `problems/背包问题完全背包一维.md`

```python
def complete_knapsack(N, bag_weight, weight, value):
    dp = [0] * (bag_weight + 1)
    for i in range(N):
        for j in range(weight[i], bag_weight + 1):
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    return dp[bag_weight]

# Input handling

N, bag_weight = map(int, input().split())
weight, value = [], []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

print(complete_knapsack(N, bag_weight, weight, value))

```

## Key Source Files in the Repository

| File | Description | Link |
|------|-------------|------|
| `problems/背包问题理论基础完全背包.md` | 2-D DP derivation for unbounded knapsack, including state definition and traversal order | [完全背包二维](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/背包问题理论基础完全背包.md) |
| `problems/背包问题完全背包一维.md` | 1-D rolling DP for complete knapsack, demonstrates interchangeable loop orders | [完全背包一维](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/背包问题完全背包一维.md) |
| `problems/背包理论基础01背包-2.md` | 0-1 knapsack with rolling array, emphasizes descending capacity iteration | [01背包滚动数组](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/背包理论基础01背包-2.md) |
| `problems/背包理论基础多重背包.md` | Bounded knapsack conversion to 0-1 items and resulting DP pattern | [多重背包](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/背包理论基础多重背包.md) |

## Summary

- **State Definition**: All variants use `dp[i][j]` (or compressed `dp[j]`) to represent maximum value for first `i` items at capacity `j`.
- **Transition Difference**: 0-1 knapsack uses `dp[i-1][j-w[i]]` (previous row) while complete knapsack uses `dp[i][j-w[i]]` (current row) to enable item reuse.
- **Loop Direction**: 0-1 knapsack requires **descending** capacity iteration in 1-D implementations to prevent multiple uses; complete knapsack allows **ascending** or descending order.
- **Space Optimization**: Both variants compress to `O(W)` space using rolling arrays, but initialization differs—complete knapsack pre-fills unlimited copies of the first item.
- **Multiple Knapsack**: Convert bounded items into multiple 0-1 items or apply nested loops with descending capacity traversal.

## Frequently Asked Questions

### What is the difference between 0-1 knapsack and complete knapsack in terms of state transition?

The 0-1 knapsack transition `dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])` references the previous row (`i-1`) to ensure each item is used at most once. The complete knapsack transition `dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])` references the current row (`i`), allowing the algorithm to consider using the same item again within the same iteration.

### Why must 0-1 knapsack iterate capacity in descending order when using a 1-D array?

When compressing the 2-D DP into a 1-D array, iterating capacity **descending** (from `W` down to `w[i]`) prevents overwriting `dp[j - w[i]]` before it is used to compute `dp[j]`. According to the source code in `problems/背包理论基础01背包-2.md`, this ensures each item is only considered once per capacity level, maintaining the 0-1 constraint.

### Can complete knapsack use either ascending or descending capacity iteration?

Yes. The repository's `problems/背包问题完全背包一维.md` explicitly demonstrates that both "item-outer, capacity-inner" and "capacity-outer, item-inner" loops produce correct results. Because complete knapsack references `dp[i][j-w[i]]` (current row), updating `dp[j]` with ascending order actually facilitates unlimited reuse, which is the desired behavior.

### How does the repository handle multiple knapsack problems with limited item counts?

The `problems/背包理论基础多重背包.md` file recommends converting each item with count `cnt[i]` into `cnt[i]` separate 0-1 items, then applying standard 0-1 knapsack logic. Alternatively, it uses a nested loop `for k in range(1, cnt[i]+1)` inside the capacity iteration, maintaining the descending capacity rule to ensure the bounded constraint is respected in 1-D implementations.