# Bounded vs Unbounded Knapsack in Dynamic Programming: Key Differences and Implementation

> Master bounded 0-1 vs unbounded knapsack dynamic programming. Understand key differences in item multiplicity and DP transitions for efficient problem-solving.

- Repository: [Yudong Jin/hello-algo](https://github.com/krahets/hello-algo)
- Tags: tutorial
- Published: 2026-02-25

---

**The fundamental difference between bounded (0-1) and unbounded knapsack problems lies in item multiplicity: 0-1 knapsack restricts each item to at most one use, requiring DP transitions from the previous row, while unbounded knapsack allows unlimited copies, enabling transitions within the same row.**

The knapsack problem family demonstrates how subtle constraint changes fundamentally alter dynamic programming approaches. In the `krahets/hello-algo` repository, both variations are implemented across multiple languages, revealing the critical distinction in state transitions and iteration order that separates these two classic optimization problems.

## Item Multiplicity: The Core Distinction

### 0-1 Knapsack (Bounded)

Each item can be selected **at most once**. This constraint forces the DP to consider whether including an item consumes that opportunity permanently. Once you place an item in the knapsack, you cannot draw from that same item again.

### Unbounded Knapsack

Any item can be taken **an unlimited number of times**. This allows the algorithm to reconsider the same item repeatedly as capacity permits, similar to making change with coins where you can use multiple quarters of the same denomination.

## Dynamic Programming State Transitions

The mathematical formulation reveals the implementation difference. Both use `dp[i][c]` representing the maximum value using the first `i` items with capacity `c`.

### 0-1 Knapsack Transition

When selecting item `i`, we must draw from the previous row since the item cannot be reused:

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

```

The term `dp[i-1][c-w[i-1]]` ensures we look at the state *before* considering item `i`, preventing multiple uses.

### Unbounded Knapsack Transition

When selecting item `i`, we stay on the same row, allowing immediate reuse:

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

```

Note the critical difference: `dp[i][c-w[i-1]]` (current row) vs `dp[i-1][c-w[i-1]]` (previous row). This single index change enables unlimited item selection.

## Space Optimization and Iteration Order

Both variations support **O(cap)** space optimization using 1-D arrays, but require opposite iteration directions to maintain correctness.

### 0-1 Knapsack: Backward Iteration

To prevent overwriting values still needed from the previous iteration, iterate backwards through capacity. In `codes/zig/chapter_dynamic_programming/knapsack.zig`, the space-optimized implementation uses:

```zig
for (1..n + 1) |i| {
    var c = cap;
    while (c >= wgt[i - 1]) : (c -= 1) {
        dp[c] = @max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
    }
}

```

The backward iteration ensures `dp[c - wgt[i - 1]]` refers to the value from the previous item (not yet updated in this iteration).

### Unbounded Knapsack: Forward Iteration

To allow reuse of the current item, iterate forwards so updated values are immediately available. In `codes/zig/chapter_dynamic_programming/unbounded_knapsack.zig`:

```zig
for (1..n + 1) |i| {
    for (wgt[i - 1]..cap + 1) |c| {
        dp[c] = @max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
    }
}

```

Forward iteration intentionally uses the updated value at `dp[c - wgt[i - 1]]`, allowing the same item to be counted multiple times as capacity increases.

## Implementation Examples from hello-algo

### Zig Implementation

The repository provides complete implementations in `codes/zig/chapter_dynamic_programming/knapsack.zig` for the bounded variant and `codes/zig/chapter_dynamic_programming/unbounded_knapsack.zig` for the unbounded version.

The bounded implementation uses the previous row reference:

```zig
// From knapsack.zig - bounded variant
fn knapsackDP(comptime wgt: []i32, val: []i32, comptime cap: usize) i32 {
    const n = wgt.len;
    var dp = [_][cap + 1]i32{[_]i32{0} ** (cap + 1)} ** (n + 1);
    for (1..n + 1) |i| {
        for (1..cap + 1) |c| {
            if (wgt[i - 1] > c) dp[i][c] = dp[i - 1][c]
            else dp[i][c] = @max(dp[i - 1][c],
                                 dp[i - 1][c - @intCast(wgt[i - 1])] + val[i - 1]);
        }
    }
    return dp[n][cap];
}

```

The unbounded version in `unbounded_knapsack.zig` modifies only the transition to use `dp[i][c - wgt[i-1]]` instead of `dp[i - 1][c - wgt[i-1]]`:

```zig
// From unbounded_knapsack.zig - unbounded variant
fn unboundedKnapsackDP(comptime wgt: []i32, val: []i32, comptime cap: usize) i32 {
    const n = wgt.len;
    var dp = [_][cap + 1]i32{[_]i32{0} ** (cap + 1)} ** (n + 1);
    for (1..n + 1) |i| {
        for (1..cap + 1) |c| {
            if (wgt[i - 1] > c) dp[i][c] = dp[i - 1][c]
            else dp[i][c] = @max(dp[i - 1][c],
                                 dp[i][c - @intCast(wgt[i - 1])] + val[i - 1]);
        }
    }
    return dp[n][cap];
}

```

### TypeScript Implementation

The TypeScript implementations in [`codes/typescript/chapter_dynamic_programming/knapsack.ts`](https://github.com/krahets/hello-algo/blob/main/codes/typescript/chapter_dynamic_programming/knapsack.ts) and [`codes/typescript/chapter_dynamic_programming/unbounded_knapsack.ts`](https://github.com/krahets/hello-algo/blob/main/codes/typescript/chapter_dynamic_programming/unbounded_knapsack.ts) follow identical logic.

Bounded version using previous row:

```typescript
// From knapsack.ts
function knapsackDP(wgt: number[], val: number[], cap: number): number {
    const n = wgt.length;
    const dp = Array.from({ length: n + 1 }, () => Array(cap + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        for (let c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) dp[i][c] = dp[i - 1][c];
            else dp[i][c] = Math.max(dp[i - 1][c],
                                    dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
        }
    }
    return dp[n][cap];
}

```

Unbounded version with same-row transition:

```typescript
// From unbounded_knapsack.ts
function unboundedKnapsackDP(wgt: number[], val: number[], cap: number): number {
    const n = wgt.length;
    const dp = Array.from({ length: n + 1 }, () => Array(cap + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        for (let c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) dp[i][c] = dp[i - 1][c];
            else dp[i][c] = Math.max(dp[i - 1][c],
                                    dp[i][c - wgt[i - 1]] + val[i - 1]);
        }
    }
    return dp[n][cap];
}

```

## Summary

- **Item multiplicity** defines the distinction: 0-1 knapsack allows each item once, while unbounded permits unlimited copies.
- **State transition** differs critically: bounded uses `dp[i-1][c-w[i-1]]` (previous row), unbounded uses `dp[i][c-w[i-1]]` (current row).
- **Iteration direction** for space-optimized 1-D DP: bounded requires backward iteration to prevent reuse, unbounded uses forward iteration to enable reuse.
- **Source implementations** in `krahets/hello-algo` demonstrate these patterns in Zig (`knapsack.zig` vs `unbounded_knapsack.zig`) and TypeScript ([`knapsack.ts`](https://github.com/krahets/hello-algo/blob/main/knapsack.ts) vs [`unbounded_knapsack.ts`](https://github.com/krahets/hello-algo/blob/main/unbounded_knapsack.ts)).

## Frequently Asked Questions

### Can I solve unbounded knapsack by simply running 0-1 knapsack multiple times?

No, because 0-1 knapsack explicitly prevents item reuse through its state transition. While you could theoretically duplicate items to simulate unbounded behavior, this becomes computationally inefficient with large capacities. The unbounded knapsack DP formulation uses `dp[i][c-w[i-1]]` to naturally allow unlimited selections within a single pass, as implemented in [`unbounded_knapsack.ts`](https://github.com/krahets/hello-algo/blob/main/unbounded_knapsack.ts).

### Why does 0-1 knapsack iterate backwards while unbounded iterates forwards?

In the space-optimized 1-D array implementation, backward iteration for 0-1 knapsack ensures that `dp[c - wgt[i-1]]` refers to the value from the previous item (not yet updated in this iteration). Forward iteration for unbounded knapsack intentionally uses the updated value at `dp[c - wgt[i-1]]`, allowing the same item to be counted multiple times as capacity increases, as shown in `codes/zig/chapter_dynamic_programming/unbounded_knapsack.zig`.

### Which real-world problems map to unbounded vs bounded knapsack?

Coin change problems (finding minimum coins to make amount) and rod cutting problems typically map to unbounded knapsack because you can use multiple coins of the same denomination or cut multiple pieces of the same length. Classic resource allocation with unique assets, subset sum problems, and equipment selection with single units map to 0-1 knapsack, as documented in [`docs/chapter_dynamic_programming/knapsack_problem.md`](https://github.com/krahets/hello-algo/blob/main/docs/chapter_dynamic_programming/knapsack_problem.md).

### Are the time and space complexities different between the two variations?

Both variations have **O(n × cap)** time complexity and **O(n × cap)** space complexity for the standard 2-D DP implementation, or **O(cap)** space for the optimized 1-D array approach. The difference lies not in asymptotic complexity but in the state transition logic and iteration direction required to achieve correct results, as illustrated in the `krahets/hello-algo` source code.