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

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:

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:

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:

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:

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:

// 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]]:

// 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 and codes/typescript/chapter_dynamic_programming/unbounded_knapsack.ts follow identical logic.

Bounded version using previous row:

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

// 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 vs 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.

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.

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.

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