Data Structures & AlgorithmsKnapsack Problems

Knapsack Problems — Resource-Constrained Optimization

LevelIntermediate

Duration90 mins

TopicKnapsack Problems

3 / 4

Unbounded Knapsack — Unlimited Item Selections

When Items Have Infinite Supply

In the 0/1 Knapsack problem, each item is unique—once you take it, it's gone. But many real-world optimization problems don't have this restriction. A vending machine can dispense multiple copies of the same drink. A warehouse can fulfill multiple units of the same product. A cable company has unlimited lengths of each cable type.

The Unbounded Knapsack (also called the Complete Knapsack) removes the single-selection constraint: each item type can be selected zero or more times. This seemingly small change fundamentally alters the problem structure and, crucially, simplifies the solution.

This variant appears in numerous practical scenarios:

Coin change problems: Make change using coins of various denominations
Rod cutting: Cut a rod into pieces to maximize value
Resource allocation: Allocate budget across programs with repeatable investments
Stock cutting: Cut material from standard rolls to minimize waste

What You Will Learn

By the end of this page, you will understand how unlimited item selection changes the knapsack recurrence, why this actually simplifies the solution to 1D space, and how to recognize and solve unbounded knapsack variants. You'll also see the connection between unbounded knapsack and the coin change problem.

The Unbounded Knapsack Problem

Given:

A set of n item types, where type i has:
- Weight: w[i] (positive integer)
- Value: v[i] (positive integer)
A knapsack with maximum capacity W
Unlimited copies of each item type available

Find: A selection of items (with possible repetition) that maximizes total value without exceeding capacity.

Mathematical Formulation:

$$\text{maximize } \sum_{i=1}^{n} x_i \cdot v[i]$$

$$\text{subject to } \sum_{i=1}^{n} x_i \cdot w[i] \leq W$$

$$x_i \geq 0 \text{ (integer for each item type)}$$

The key difference from 0/1 Knapsack: each $x_i$ can be any non-negative integer, not just 0 or 1.

Example Unbounded Knapsack Instance
Item Type	Weight	Value	Value/Weight
Type A	2	5	2.5
Type B	3	8	2.67
Type C	5	13	2.6

Capacity: W = 10

Possible Solutions:

5 copies of Type A: weight = 10, value = 25
3 copies of Type B + 1 copy of Type A: weight = 9 + 2 = 11 ✗ (exceeds)
3 copies of Type B: weight = 9, value = 24
2 copies of Type C: weight = 10, value = 26 ← Optimal
1 Type B + 1 Type C + 1 Type A: weight = 10, value = 26 ← Also Optimal

Notice that multiple optimal solutions may exist, and the greedy choice (highest ratio first) doesn't always win.

From 0/1 to Unbounded: The Key Change

The fundamental difference between 0/1 and Unbounded Knapsack lies in what happens after selecting an item.

In 0/1 Knapsack: When we include item i, we move to items 1..i-1—item i is consumed and unavailable.

dp[i][c] = max(
    dp[i-1][c],              // Exclude item i
    dp[i-1][c-w[i]] + v[i]   // Include item i, move on
)

In Unbounded Knapsack: When we include item i, it remains available for future selections!

dp[i][c] = max(
    dp[i-1][c],              // Never take item i
    dp[i][c-w[i]] + v[i]     // Take one copy of item i (may take more)
)

Notice the subtle but crucial change: the "include" case refers to dp[i][c-w[i]] instead of dp[i-1][c-w[i]]. We stay at item i because we might want to take another copy!

The Critical Insight

In 0/1 Knapsack, including item i is an exit from that item. In Unbounded Knapsack, including item i is a loop—we can include it again and again until capacity is exhausted or other items become better choices.

0/1 Knapsack

•Each item: take or skip (binary)
•Include → consume item, move to i-1
•Decision: 'Should I use my one chance?'
•State: (items considered, capacity)

Unbounded Knapsack

•Each item: take 0, 1, 2, ... copies
•Include → item still available
•Decision: 'Should I add one more?'
•State: just (capacity) suffices!

The Two-Dimensional Recurrence

Let's first develop the natural 2D recurrence (analogous to 0/1 Knapsack), then show how it simplifies.

State Definition: dp[i][c] = Maximum value using item types 1..i with capacity c

Recurrence:

Unbounded Knapsack 2D Recurrence
dp[i][c] = max(
    dp[i-1][c],              // Option 1: Don't use item i at all
    dp[i][c-w[i]] + v[i]     // Option 2: Use at least one copy of item i
)                            //           (note: dp[i], not dp[i-1])
 
// Base cases:
dp[0][c] = 0 for all c      // No items available → zero value
dp[i][0] = 0 for all i      // Zero capacity → can't take anything
 
// Condition for Option 2: w[i] <= c

Why Option 2 References dp[i] Instead of dp[i-1]:

When we take one copy of item i, we use capacity w[i] and gain value v[i]. But crucially, item i is still available. So the remaining subproblem—finding the best way to fill capacity c - w[i] using items 1..i—still includes item i.

By referencing dp[i][c-w[i]], we allow for taking another copy of item i. This creates an implicit loop:

dp[i][10] might take item i, referencing dp[i][7]
dp[i][7] might take item i again, referencing dp[i][4]
And so on, until capacity is exhausted or excluding the item becomes better

This recursive structure automatically considers all possible quantities of each item.

Dependency Change and Fill Order

In 0/1 Knapsack, dp[i][c] depends only on row i-1 (previous row). In Unbounded Knapsack, dp[i][c] also depends on dp[i][c-w[i]] (same row, earlier column). This means we must fill each row left-to-right to ensure dependencies are computed first.

Simplification to One Dimension

Here's a beautiful insight: for Unbounded Knapsack, we don't need the item dimension at all!

Since every item is always available, the only question is: "Given capacity c, what's the maximum value I can achieve using any combination of items?"

Simplified State: dp[c] = Maximum value achievable with capacity exactly c

Simplified Recurrence:

Unbounded Knapsack 1D Recurrence
// For each capacity c from 1 to W:
dp[c] = max over all items i with w[i] <= c of:
        dp[c - w[i]] + v[i]
 
// In code form:
dp[c] = max(dp[c], dp[c - w[i]] + v[i]) for each item i where w[i] <= c
 
// Base case:
dp[0] = 0  // Zero capacity → zero value
 
// Final answer:
dp[W]

Why This Works:

For any capacity c, we try adding one unit of each item type that fits. For item i, adding one unit gives us v[i] plus the optimal value for the remaining capacity c - w[i]. Since dp[c - w[i]] is computed before dp[c] (we process capacities in increasing order), and since items are always available, this correctly finds the optimal combination.

The implicit assumption is that we can use any item any number of times—which is exactly the Unbounded Knapsack property!

Complexity:

Time: O(n × W) — for each capacity, try all n items
Space: O(W) — just one 1D array

This is the same time complexity as 0/1 Knapsack but with reduced space and simpler code.

The Power of Simplified State

Dropping from 2D to 1D is possible because item availability is uniform—all items are always available. When constraints are uniform across the decision sequence, the state can often be simplified.

Complete Implementation

Let's implement both the 2D (conceptually clearer) and 1D (optimized) versions of Unbounded Knapsack.

unbounded_knapsack.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
def unbounded_knapsack_2d(weights: list[int], values: list[int], capacity: int) -> int:
    """
    Unbounded Knapsack using 2D DP (for clarity).
    Each item type can be selected unlimited times.
    
    Time: O(n * W), Space: O(n * W)
    """
    n = len(weights)
    
    # dp[i][c] = max value using item types 0..i-1 with capacity c
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        weight_i = weights[i - 1]
        value_i = values[i - 1]
        
        for c in range(capacity + 1):
            # Option 1: Don't use item i at all
            dp[i][c] = dp[i - 1][c]
            
            # Option 2: Use at least one copy of item i
            if weight_i <= c:
                # Key difference: dp[i] not dp[i-1]!
                dp[i][c] = max(dp[i][c], dp[i][c - weight_i] + value_i)
    
    return dp[n][capacity]
 
 
def unbounded_knapsack_1d(weights: list[int], values: list[int], capacity: int) -> int:
    """
    Unbounded Knapsack using optimized 1D DP.
    Each item type can be selected unlimited times.
    
    Time: O(n * W), Space: O(W)
    """
    # dp[c] = max value with capacity c
    dp = [0] * (capacity + 1)
    
    # For each capacity from 1 to W
    for c in range(1, capacity + 1):
        # Try adding one unit of each item
        for i in range(len(weights)):
            if weights[i] <= c:
                dp[c] = max(dp[c], dp[c - weights[i]] + values[i])
    
    return dp[capacity]
 
 
def unbounded_knapsack_with_items(
    weights: list[int], 
    values: list[int], 
    capacity: int
) -> tuple[int, dict[int, int]]:
    """
    Unbounded Knapsack with item selection tracking.
    
    Returns:
        Tuple of (max_value, dict mapping item index to count)
    """
    # dp[c] = max value with capacity c
    dp = [0] * (capacity + 1)
    # choice[c] = which item was last added to achieve dp[c]
    choice = [-1] * (capacity + 1)
    
    for c in range(1, capacity + 1):
        for i in range(len(weights)):
            if weights[i] <= c:
                candidate = dp[c - weights[i]] + values[i]
                if candidate > dp[c]:
                    dp[c] = candidate
                    choice[c] = i
    
    # Reconstruct item counts
    item_counts: dict[int, int] = {}
    remaining = capacity
    
    while remaining > 0 and choice[remaining] != -1:
        item_idx = choice[remaining]
        item_counts[item_idx] = item_counts.get(item_idx, 0) + 1
        remaining -= weights[item_idx]
    
    return dp[capacity], item_counts
 
 
# Example usage
if __name__ == "__main__":
    weights = [2, 3, 5]
    values = [5, 8, 13]
    capacity = 10
    
    max_val_2d = unbounded_knapsack_2d(weights, values, capacity)
    max_val_1d = unbounded_knapsack_1d(weights, values, capacity)
    max_val, counts = unbounded_knapsack_with_items(weights, values, capacity)
    
    print(f"Maximum value (2D): {max_val_2d}")
    print(f"Maximum value (1D): {max_val_1d}")
    print(f"Maximum value with items: {max_val}")
    print("Selected items:")
    for idx, count in counts.items():
        print(f"  Item {idx} (w={weights[idx]}, v={values[idx]}): {count} copies")

Connection to Coin Change

The Unbounded Knapsack problem is intimately connected to the classic Coin Change problem. In fact, coin change is a special case of unbounded knapsack!

Coin Change Problem: Given coin denominations [c₁, c₂, ..., cₙ] and a target amount A, find the minimum number of coins to make exactly A.

Mapping to Unbounded Knapsack:

Item types → Coin denominations
Weight → Coin value (denomination)
Value → -1 (we want to minimize count)
Capacity → Target amount A

Alternatively, think of it as unbounded knapsack where:

Each coin has weight = denomination and value = 1
Goal: minimize total value (count) to achieve exactly capacity (amount)

coin_change.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def coin_change_min_coins(coins: list[int], amount: int) -> int:
    """
    Find minimum number of coins to make exact amount.
    Returns -1 if impossible.
    
    This is Unbounded Knapsack where:
    - weights = coin denominations
    - we minimize count instead of maximizing value
    """
    # dp[a] = minimum coins to make amount a
    # Initialize with infinity (impossible)
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0  # Zero coins to make amount 0
    
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and dp[a - coin] != INF:
                dp[a] = min(dp[a], dp[a - coin] + 1)
    
    return dp[amount] if dp[amount] != INF else -1
 
 
def coin_change_count_ways(coins: list[int], amount: int) -> int:
    """
    Count the number of ways to make exact amount.
    Order doesn't matter: [1,2] and [2,1] are the same way.
    
    Different from unbounded knapsack DP order!
    """
    # dp[a] = number of ways to make amount a
    dp = [0] * (amount + 1)
    dp[0] = 1  # One way to make 0: use no coins
    
    # IMPORTANT: Iterate coins in outer loop to avoid counting permutations
    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] += dp[a - coin]
    
    return dp[amount]
 
 
# Example
if __name__ == "__main__":
    coins = [1, 5, 10, 25]  # US coins (cents)
    amount = 30
    
    min_coins = coin_change_min_coins(coins, amount)
    num_ways = coin_change_count_ways(coins, amount)
    
    print(f"Minimum coins for {amount} cents: {min_coins}")  # 2 (25 + 5)
    print(f"Number of ways to make {amount} cents: {num_ways}")

Critical Difference: Counting Combinations vs Permutations

When counting ways to make an amount, loop order matters!

Coins outer, amounts inner: Counts combinations (1+2 = 2+1). Each coin type is 'introduced' once, preventing duplicate orderings.

Amounts outer, coins inner: Counts permutations (1+2 ≠ 2+1). Same combination counted multiple times with different orderings.

For min coins, either order works. For counting combinations, coins must be outer.

The Rod Cutting Problem

Another classic unbounded knapsack variant is the Rod Cutting problem, often used to introduce DP in algorithm courses.

Problem Statement: Given a rod of length n and a price table p[i] giving the price of a piece of length i, determine the maximum revenue obtainable by cutting the rod and selling the pieces.

Mapping to Unbounded Knapsack:

Item types: Pieces of length 1, 2, 3, ..., n
Weight: Length of piece
Value: Price of piece
Capacity: Total rod length
Goal: Maximize total price

rod_cutting.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def rod_cutting(prices: list[int], length: int) -> int:
    """
    Find maximum revenue from cutting a rod of given length.
    prices[i] = price for a piece of length i+1
    
    This is exactly Unbounded Knapsack!
    """
    # dp[l] = max revenue from rod of length l
    dp = [0] * (length + 1)
    
    for l in range(1, length + 1):
        # Try each possible cut
        for cut in range(1, l + 1):
            if cut <= len(prices):
                dp[l] = max(dp[l], prices[cut - 1] + dp[l - cut])
    
    return dp[length]
 
 
def rod_cutting_with_cuts(prices: list[int], length: int) -> tuple[int, list[int]]:
    """
    Rod cutting with cut reconstruction.
    Returns (max_revenue, list of piece lengths).
    """
    dp = [0] * (length + 1)
    first_cut = [0] * (length + 1)  # first_cut[l] = size of first piece for length l
    
    for l in range(1, length + 1):
        for cut in range(1, min(l, len(prices)) + 1):
            candidate = prices[cut - 1] + dp[l - cut]
            if candidate > dp[l]:
                dp[l] = candidate
                first_cut[l] = cut
    
    # Reconstruct the cuts
    pieces = []
    remaining = length
    while remaining > 0:
        pieces.append(first_cut[remaining])
        remaining -= first_cut[remaining]
    
    return dp[length], pieces
 
 
# Example
if __name__ == "__main__":
    # Price table: prices[i] = price for piece of length i+1
    prices = [1, 5, 8, 9, 10, 17, 17, 20]  # lengths 1-8
    rod_length = 8
    
    max_rev, cuts = rod_cutting_with_cuts(prices, rod_length)
    print(f"Maximum revenue for rod of length {rod_length}: {max_rev}")
    print(f"Optimal cuts: {cuts}")
    print(f"Verification: {' + '.join(str(prices[c-1]) for c in cuts)} = {sum(prices[c-1] for c in cuts)}")

Insight:

Rod cutting demonstrates how the same underlying algorithm (unbounded knapsack) appears in different guises. The key recognition is:

We have "item types" (piece lengths)
Each type can be used multiple times (we can cut multiple pieces of the same length)
We want to maximize value (total price) within a constraint (total length)

Once you recognize this pattern, the solution follows directly.

0/1 vs Unbounded Knapsack Comparison

Let's crystallize the key differences and similarities between the two knapsack variants:

0/1 vs Unbounded Knapsack
Aspect	0/1 Knapsack	Unbounded Knapsack
Item selection	Each item used at most once	Each item type used any number of times
Decision variable	Binary: include (1) or exclude (0)	Integer: count of each item type
Recurrence structure	dp[i-1][c-w] (move to previous items)	dp[i][c-w] (stay at same item)
Minimal state	2D: (item index, capacity)	1D: (capacity) suffices
Fill order	Row by row, any order within row	Capacity increasing (left to right)
Time complexity	O(n × W)	O(n × W)
Space (optimized)	O(W) with 1D rolling array	O(W) naturally
Greedy works?	No	No (usually)

Memory Trick for Recurrence

0/1 Knapsack: Including item i is like saying goodbye—you move to dp[i-1].

Unbounded Knapsack: Including item i is like taking a sample from an infinite pile—you stay at dp[i] (or just the capacity dimension).

Summary: Unbounded Knapsack Mastery

We've thoroughly explored the Unbounded Knapsack problem and its relationship to the 0/1 variant, as well as its manifestations in coin change and rod cutting.

Key Takeaways

•Unlimited selection changes the recurrence: The 'include' case stays at the same item (dp[i]) rather than moving to previous items (dp[i-1]).
•State simplifies to 1D: Since all items are always available, we only need to track capacity, not which items we've considered.
•Fill order matters: We must fill capacities in increasing order (left to right) because dp[c] depends on dp[c - w[i]].
•Coin Change is a special case: Mapping denominations to weights and minimizing count to maximizing negative values transforms coin change to unbounded knapsack.
•Rod Cutting is the same pattern: Piece lengths are item types, prices are values, rod length is capacity.
•Recognize the pattern: When items can be reused and you're optimizing under a capacity constraint, think unbounded knapsack.

What's Next:

We'll explore the Subset Sum problem—a knapsack variant where all items have value equal to their weight. This special case has unique properties and appears frequently in interview and competition problems.

Page Complete

You now understand the Unbounded Knapsack problem, its simplified 1D formulation, and how classic problems like Coin Change and Rod Cutting are instances of this fundamental pattern.

3 / 4

Loading learning content...

Data Structures & AlgorithmsKnapsack Problems

Knapsack Problems — Resource-Constrained Optimization

LevelIntermediate

Duration90 mins

TopicKnapsack Problems

3 / 4

Unbounded Knapsack — Unlimited Item Selections

When Items Have Infinite Supply

This variant appears in numerous practical scenarios:

Coin change problems: Make change using coins of various denominations
Rod cutting: Cut a rod into pieces to maximize value
Resource allocation: Allocate budget across programs with repeatable investments
Stock cutting: Cut material from standard rolls to minimize waste

What You Will Learn

The Unbounded Knapsack Problem

Given:

A set of n item types, where type i has:
- Weight: w[i] (positive integer)
- Value: v[i] (positive integer)
A knapsack with maximum capacity W
Unlimited copies of each item type available

Find: A selection of items (with possible repetition) that maximizes total value without exceeding capacity.

Mathematical Formulation:

$$\text{maximize } \sum_{i=1}^{n} x_i \cdot v[i]$$

$$\text{subject to } \sum_{i=1}^{n} x_i \cdot w[i] \leq W$$

$$x_i \geq 0 \text{ (integer for each item type)}$$

The key difference from 0/1 Knapsack: each $x_i$ can be any non-negative integer, not just 0 or 1.

Example Unbounded Knapsack Instance
Item Type	Weight	Value	Value/Weight
Type A	2	5	2.5
Type B	3	8	2.67
Type C	5	13	2.6

Capacity: W = 10

Possible Solutions:

5 copies of Type A: weight = 10, value = 25
3 copies of Type B + 1 copy of Type A: weight = 9 + 2 = 11 ✗ (exceeds)
3 copies of Type B: weight = 9, value = 24
2 copies of Type C: weight = 10, value = 26 ← Optimal
1 Type B + 1 Type C + 1 Type A: weight = 10, value = 26 ← Also Optimal

Notice that multiple optimal solutions may exist, and the greedy choice (highest ratio first) doesn't always win.

From 0/1 to Unbounded: The Key Change

The fundamental difference between 0/1 and Unbounded Knapsack lies in what happens after selecting an item.

In 0/1 Knapsack: When we include item i, we move to items 1..i-1—item i is consumed and unavailable.

dp[i][c] = max(
    dp[i-1][c],              // Exclude item i
    dp[i-1][c-w[i]] + v[i]   // Include item i, move on
)

In Unbounded Knapsack: When we include item i, it remains available for future selections!

dp[i][c] = max(
    dp[i-1][c],              // Never take item i
    dp[i][c-w[i]] + v[i]     // Take one copy of item i (may take more)
)

Notice the subtle but crucial change: the "include" case refers to dp[i][c-w[i]] instead of dp[i-1][c-w[i]]. We stay at item i because we might want to take another copy!

The Critical Insight

0/1 Knapsack

•Each item: take or skip (binary)
•Include → consume item, move to i-1
•Decision: 'Should I use my one chance?'
•State: (items considered, capacity)

Unbounded Knapsack

•Each item: take 0, 1, 2, ... copies
•Include → item still available
•Decision: 'Should I add one more?'
•State: just (capacity) suffices!

The Two-Dimensional Recurrence

Let's first develop the natural 2D recurrence (analogous to 0/1 Knapsack), then show how it simplifies.

State Definition: dp[i][c] = Maximum value using item types 1..i with capacity c

Recurrence:

Unbounded Knapsack 2D Recurrence
dp[i][c] = max(
    dp[i-1][c],              // Option 1: Don't use item i at all
    dp[i][c-w[i]] + v[i]     // Option 2: Use at least one copy of item i
)                            //           (note: dp[i], not dp[i-1])
 
// Base cases:
dp[0][c] = 0 for all c      // No items available → zero value
dp[i][0] = 0 for all i      // Zero capacity → can't take anything
 
// Condition for Option 2: w[i] <= c

Why Option 2 References dp[i] Instead of dp[i-1]:

By referencing dp[i][c-w[i]], we allow for taking another copy of item i. This creates an implicit loop:

dp[i][10] might take item i, referencing dp[i][7]
dp[i][7] might take item i again, referencing dp[i][4]
And so on, until capacity is exhausted or excluding the item becomes better

This recursive structure automatically considers all possible quantities of each item.

Dependency Change and Fill Order

Simplification to One Dimension

Here's a beautiful insight: for Unbounded Knapsack, we don't need the item dimension at all!

Since every item is always available, the only question is: "Given capacity c, what's the maximum value I can achieve using any combination of items?"

Simplified State: dp[c] = Maximum value achievable with capacity exactly c

Simplified Recurrence:

Unbounded Knapsack 1D Recurrence
// For each capacity c from 1 to W:
dp[c] = max over all items i with w[i] <= c of:
        dp[c - w[i]] + v[i]
 
// In code form:
dp[c] = max(dp[c], dp[c - w[i]] + v[i]) for each item i where w[i] <= c
 
// Base case:
dp[0] = 0  // Zero capacity → zero value
 
// Final answer:
dp[W]

Why This Works:

The implicit assumption is that we can use any item any number of times—which is exactly the Unbounded Knapsack property!

Complexity:

Time: O(n × W) — for each capacity, try all n items
Space: O(W) — just one 1D array

This is the same time complexity as 0/1 Knapsack but with reduced space and simpler code.

The Power of Simplified State

Dropping from 2D to 1D is possible because item availability is uniform—all items are always available. When constraints are uniform across the decision sequence, the state can often be simplified.

Complete Implementation

Let's implement both the 2D (conceptually clearer) and 1D (optimized) versions of Unbounded Knapsack.

unbounded_knapsack.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
def unbounded_knapsack_2d(weights: list[int], values: list[int], capacity: int) -> int:
    """
    Unbounded Knapsack using 2D DP (for clarity).
    Each item type can be selected unlimited times.
    
    Time: O(n * W), Space: O(n * W)
    """
    n = len(weights)
    
    # dp[i][c] = max value using item types 0..i-1 with capacity c
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        weight_i = weights[i - 1]
        value_i = values[i - 1]
        
        for c in range(capacity + 1):
            # Option 1: Don't use item i at all
            dp[i][c] = dp[i - 1][c]
            
            # Option 2: Use at least one copy of item i
            if weight_i <= c:
                # Key difference: dp[i] not dp[i-1]!
                dp[i][c] = max(dp[i][c], dp[i][c - weight_i] + value_i)
    
    return dp[n][capacity]
 
 
def unbounded_knapsack_1d(weights: list[int], values: list[int], capacity: int) -> int:
    """
    Unbounded Knapsack using optimized 1D DP.
    Each item type can be selected unlimited times.
    
    Time: O(n * W), Space: O(W)
    """
    # dp[c] = max value with capacity c
    dp = [0] * (capacity + 1)
    
    # For each capacity from 1 to W
    for c in range(1, capacity + 1):
        # Try adding one unit of each item
        for i in range(len(weights)):
            if weights[i] <= c:
                dp[c] = max(dp[c], dp[c - weights[i]] + values[i])
    
    return dp[capacity]
 
 
def unbounded_knapsack_with_items(
    weights: list[int], 
    values: list[int], 
    capacity: int
) -> tuple[int, dict[int, int]]:
    """
    Unbounded Knapsack with item selection tracking.
    
    Returns:
        Tuple of (max_value, dict mapping item index to count)
    """
    # dp[c] = max value with capacity c
    dp = [0] * (capacity + 1)
    # choice[c] = which item was last added to achieve dp[c]
    choice = [-1] * (capacity + 1)
    
    for c in range(1, capacity + 1):
        for i in range(len(weights)):
            if weights[i] <= c:
                candidate = dp[c - weights[i]] + values[i]
                if candidate > dp[c]:
                    dp[c] = candidate
                    choice[c] = i
    
    # Reconstruct item counts
    item_counts: dict[int, int] = {}
    remaining = capacity
    
    while remaining > 0 and choice[remaining] != -1:
        item_idx = choice[remaining]
        item_counts[item_idx] = item_counts.get(item_idx, 0) + 1
        remaining -= weights[item_idx]
    
    return dp[capacity], item_counts
 
 
# Example usage
if __name__ == "__main__":
    weights = [2, 3, 5]
    values = [5, 8, 13]
    capacity = 10
    
    max_val_2d = unbounded_knapsack_2d(weights, values, capacity)
    max_val_1d = unbounded_knapsack_1d(weights, values, capacity)
    max_val, counts = unbounded_knapsack_with_items(weights, values, capacity)
    
    print(f"Maximum value (2D): {max_val_2d}")
    print(f"Maximum value (1D): {max_val_1d}")
    print(f"Maximum value with items: {max_val}")
    print("Selected items:")
    for idx, count in counts.items():
        print(f"  Item {idx} (w={weights[idx]}, v={values[idx]}): {count} copies")

Connection to Coin Change

The Unbounded Knapsack problem is intimately connected to the classic Coin Change problem. In fact, coin change is a special case of unbounded knapsack!

Coin Change Problem: Given coin denominations [c₁, c₂, ..., cₙ] and a target amount A, find the minimum number of coins to make exactly A.

Mapping to Unbounded Knapsack:

Item types → Coin denominations
Weight → Coin value (denomination)
Value → -1 (we want to minimize count)
Capacity → Target amount A

Alternatively, think of it as unbounded knapsack where:

Each coin has weight = denomination and value = 1
Goal: minimize total value (count) to achieve exactly capacity (amount)

coin_change.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def coin_change_min_coins(coins: list[int], amount: int) -> int:
    """
    Find minimum number of coins to make exact amount.
    Returns -1 if impossible.
    
    This is Unbounded Knapsack where:
    - weights = coin denominations
    - we minimize count instead of maximizing value
    """
    # dp[a] = minimum coins to make amount a
    # Initialize with infinity (impossible)
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0  # Zero coins to make amount 0
    
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and dp[a - coin] != INF:
                dp[a] = min(dp[a], dp[a - coin] + 1)
    
    return dp[amount] if dp[amount] != INF else -1
 
 
def coin_change_count_ways(coins: list[int], amount: int) -> int:
    """
    Count the number of ways to make exact amount.
    Order doesn't matter: [1,2] and [2,1] are the same way.
    
    Different from unbounded knapsack DP order!
    """
    # dp[a] = number of ways to make amount a
    dp = [0] * (amount + 1)
    dp[0] = 1  # One way to make 0: use no coins
    
    # IMPORTANT: Iterate coins in outer loop to avoid counting permutations
    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] += dp[a - coin]
    
    return dp[amount]
 
 
# Example
if __name__ == "__main__":
    coins = [1, 5, 10, 25]  # US coins (cents)
    amount = 30
    
    min_coins = coin_change_min_coins(coins, amount)
    num_ways = coin_change_count_ways(coins, amount)
    
    print(f"Minimum coins for {amount} cents: {min_coins}")  # 2 (25 + 5)
    print(f"Number of ways to make {amount} cents: {num_ways}")

Critical Difference: Counting Combinations vs Permutations

When counting ways to make an amount, loop order matters!

Coins outer, amounts inner: Counts combinations (1+2 = 2+1). Each coin type is 'introduced' once, preventing duplicate orderings.

Amounts outer, coins inner: Counts permutations (1+2 ≠ 2+1). Same combination counted multiple times with different orderings.

For min coins, either order works. For counting combinations, coins must be outer.

The Rod Cutting Problem

Another classic unbounded knapsack variant is the Rod Cutting problem, often used to introduce DP in algorithm courses.

Mapping to Unbounded Knapsack:

Item types: Pieces of length 1, 2, 3, ..., n
Weight: Length of piece
Value: Price of piece
Capacity: Total rod length
Goal: Maximize total price

rod_cutting.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def rod_cutting(prices: list[int], length: int) -> int:
    """
    Find maximum revenue from cutting a rod of given length.
    prices[i] = price for a piece of length i+1
    
    This is exactly Unbounded Knapsack!
    """
    # dp[l] = max revenue from rod of length l
    dp = [0] * (length + 1)
    
    for l in range(1, length + 1):
        # Try each possible cut
        for cut in range(1, l + 1):
            if cut <= len(prices):
                dp[l] = max(dp[l], prices[cut - 1] + dp[l - cut])
    
    return dp[length]
 
 
def rod_cutting_with_cuts(prices: list[int], length: int) -> tuple[int, list[int]]:
    """
    Rod cutting with cut reconstruction.
    Returns (max_revenue, list of piece lengths).
    """
    dp = [0] * (length + 1)
    first_cut = [0] * (length + 1)  # first_cut[l] = size of first piece for length l
    
    for l in range(1, length + 1):
        for cut in range(1, min(l, len(prices)) + 1):
            candidate = prices[cut - 1] + dp[l - cut]
            if candidate > dp[l]:
                dp[l] = candidate
                first_cut[l] = cut
    
    # Reconstruct the cuts
    pieces = []
    remaining = length
    while remaining > 0:
        pieces.append(first_cut[remaining])
        remaining -= first_cut[remaining]
    
    return dp[length], pieces
 
 
# Example
if __name__ == "__main__":
    # Price table: prices[i] = price for piece of length i+1
    prices = [1, 5, 8, 9, 10, 17, 17, 20]  # lengths 1-8
    rod_length = 8
    
    max_rev, cuts = rod_cutting_with_cuts(prices, rod_length)
    print(f"Maximum revenue for rod of length {rod_length}: {max_rev}")
    print(f"Optimal cuts: {cuts}")
    print(f"Verification: {' + '.join(str(prices[c-1]) for c in cuts)} = {sum(prices[c-1] for c in cuts)}")

Insight:

Rod cutting demonstrates how the same underlying algorithm (unbounded knapsack) appears in different guises. The key recognition is:

We have "item types" (piece lengths)
Each type can be used multiple times (we can cut multiple pieces of the same length)
We want to maximize value (total price) within a constraint (total length)

Once you recognize this pattern, the solution follows directly.

0/1 vs Unbounded Knapsack Comparison

Let's crystallize the key differences and similarities between the two knapsack variants:

0/1 vs Unbounded Knapsack
Aspect	0/1 Knapsack	Unbounded Knapsack
Item selection	Each item used at most once	Each item type used any number of times
Decision variable	Binary: include (1) or exclude (0)	Integer: count of each item type
Recurrence structure	dp[i-1][c-w] (move to previous items)	dp[i][c-w] (stay at same item)
Minimal state	2D: (item index, capacity)	1D: (capacity) suffices
Fill order	Row by row, any order within row	Capacity increasing (left to right)
Time complexity	O(n × W)	O(n × W)
Space (optimized)	O(W) with 1D rolling array	O(W) naturally
Greedy works?	No	No (usually)

Memory Trick for Recurrence

0/1 Knapsack: Including item i is like saying goodbye—you move to dp[i-1].

Unbounded Knapsack: Including item i is like taking a sample from an infinite pile—you stay at dp[i] (or just the capacity dimension).

Summary: Unbounded Knapsack Mastery

We've thoroughly explored the Unbounded Knapsack problem and its relationship to the 0/1 variant, as well as its manifestations in coin change and rod cutting.

Key Takeaways

•Unlimited selection changes the recurrence: The 'include' case stays at the same item (dp[i]) rather than moving to previous items (dp[i-1]).
•State simplifies to 1D: Since all items are always available, we only need to track capacity, not which items we've considered.
•Fill order matters: We must fill capacities in increasing order (left to right) because dp[c] depends on dp[c - w[i]].
•Coin Change is a special case: Mapping denominations to weights and minimizing count to maximizing negative values transforms coin change to unbounded knapsack.
•Rod Cutting is the same pattern: Piece lengths are item types, prices are values, rod length is capacity.
•Recognize the pattern: When items can be reused and you're optimizing under a capacity constraint, think unbounded knapsack.

What's Next:

Page Complete

You now understand the Unbounded Knapsack problem, its simplified 1D formulation, and how classic problems like Coin Change and Rod Cutting are instances of this fundamental pattern.

3 / 4