Unbounded Knapsack: Complete Knapsack Problem
The unbounded knapsack problem, also called the complete knapsack problem, removes the single-use constraint from its 0/1 cousin. You have a knapsack with capacity W and n item types, each with a...
Key Insights
- The unbounded knapsack allows unlimited item selections, enabling a simpler 1D DP array with forward iteration—fundamentally different from the 0/1 variant’s backward traversal requirement.
- The state transition
dp[w] = max(dp[w], dp[w-weight[i]] + value[i])captures the essence: at each capacity, we can always reconsider adding any item we’ve already considered. - Many classic problems (coin change, rod cutting, ribbon cutting) are unbounded knapsack variants in disguise—recognizing this pattern unlocks efficient solutions across problem domains.
Introduction to the Unbounded Knapsack Problem
The unbounded knapsack problem, also called the complete knapsack problem, removes the single-use constraint from its 0/1 cousin. You have a knapsack with capacity W and n item types, each with a weight and value. Unlike the 0/1 variant where each item exists exactly once, here you have infinite copies of each item type. Your goal: maximize total value without exceeding capacity.
This distinction matters more than it might seem. The 0/1 knapsack requires tracking whether each specific item has been used. The unbounded version doesn’t—you only care about remaining capacity and available item types.
Real-world applications are everywhere. Cutting stock problems ask how to cut raw materials to minimize waste. Currency exchange optimizes denomination combinations. Cloud resource allocation determines optimal instance type combinations within budget constraints. Even video game inventory systems often model unbounded selection from item categories.
Problem Definition and Mathematical Formulation
Given n item types where item i has weight w[i] and value v[i], and a knapsack with capacity W, find the maximum value achievable by selecting items (with unlimited repetition) such that total weight doesn’t exceed W.
Mathematically:
- Maximize: Σ(x[i] × v[i]) for i = 0 to n-1
- Subject to: Σ(x[i] × w[i]) ≤ W
- Where: x[i] ≥ 0 and x[i] is an integer
The key constraint difference: x[i] can be any non-negative integer, not just 0 or 1.
from dataclasses import dataclass
from typing import List, Tuple
@dataclass
class Item:
weight: int
value: int
name: str = ""
@dataclass
class KnapsackProblem:
items: List[Item]
capacity: int
def validate(self) -> bool:
"""Ensure problem is well-formed."""
if self.capacity < 0:
return False
return all(item.weight > 0 and item.value >= 0 for item in self.items)
# Sample test cases
def get_test_cases() -> List[Tuple[KnapsackProblem, int]]:
return [
# (problem, expected_max_value)
(KnapsackProblem(
items=[Item(2, 5, "A"), Item(3, 8, "B"), Item(4, 9, "C")],
capacity=10
), 25), # 5 copies of item A
(KnapsackProblem(
items=[Item(1, 1, "penny"), Item(3, 4, "nickel"), Item(5, 7, "dime")],
capacity=8
), 11), # Various combinations possible
(KnapsackProblem(
items=[Item(5, 10, "heavy"), Item(2, 3, "light")],
capacity=7
), 13), # 1 heavy + 1 light
]
Recursive Solution with Memoization
The recursive approach explores all possibilities: for each item, either skip it or include it (and recurse with reduced capacity, keeping the item available for future consideration).
The overlapping subproblems become apparent quickly. Computing the maximum value for capacity 5 might happen through multiple paths: directly, after taking one item of weight 2, after taking two items of weight 1, etc. Memoization eliminates redundant computation.
from functools import lru_cache
from typing import List
def unbounded_knapsack_memo(weights: List[int], values: List[int], capacity: int) -> int:
"""
Top-down recursive solution with memoization.
Time: O(n × W), Space: O(W) for memo + O(W) recursion stack
"""
n = len(weights)
@lru_cache(maxsize=None)
def solve(remaining_capacity: int) -> int:
if remaining_capacity <= 0:
return 0
max_value = 0
for i in range(n):
if weights[i] <= remaining_capacity:
# Take item i and recurse (item remains available)
candidate = values[i] + solve(remaining_capacity - weights[i])
max_value = max(max_value, candidate)
return max_value
return solve(capacity)
# Alternative: 2D memoization (useful for item tracking)
def unbounded_knapsack_memo_2d(weights: List[int], values: List[int], capacity: int) -> int:
"""
2D memoization tracking both item index and capacity.
Useful when you need to reconstruct the solution.
"""
n = len(weights)
memo = {}
def solve(idx: int, remaining: int) -> int:
if remaining <= 0 or idx >= n:
return 0
if (idx, remaining) in memo:
return memo[(idx, remaining)]
# Option 1: Skip this item type entirely
skip = solve(idx + 1, remaining)
# Option 2: Take one of this item (stay at same index for unlimited takes)
take = 0
if weights[idx] <= remaining:
take = values[idx] + solve(idx, remaining - weights[idx])
memo[(idx, remaining)] = max(skip, take)
return memo[(idx, remaining)]
return solve(0, capacity)
Time complexity is O(n × W) where n is item count and W is capacity. Space complexity includes O(W) for memoization plus O(W) worst-case recursion depth.
Dynamic Programming: Tabulation Approach
The bottom-up approach builds solutions incrementally. We define dp[w] as the maximum value achievable with exactly capacity w. The recurrence relation is elegant:
dp[w] = max(dp[w], dp[w - weight[i]] + value[i]) for all valid i
Here’s why a 1D array works: when we compute dp[w], we reference dp[w - weight[i]], which represents a smaller capacity. Since items are unlimited, it doesn’t matter if we’ve already “used” an item at that smaller capacity—we can use it again.
from typing import List, Tuple
def unbounded_knapsack_dp(weights: List[int], values: List[int], capacity: int) -> int:
"""
Bottom-up DP solution.
Time: O(n × W), Space: O(W)
"""
n = len(weights)
dp = [0] * (capacity + 1)
# For each capacity from 1 to W
for w in range(1, capacity + 1):
# Try each item
for i in range(n):
if weights[i] <= w:
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
def unbounded_knapsack_dp_verbose(weights: List[int], values: List[int], capacity: int) -> Tuple[int, List[List[int]]]:
"""
DP solution with step-by-step table for visualization.
Returns (max_value, table_history)
"""
n = len(weights)
dp = [0] * (capacity + 1)
history = [dp.copy()]
print(f"Items: weights={weights}, values={values}")
print(f"Capacity: {capacity}")
print(f"\nInitial: {dp}")
for w in range(1, capacity + 1):
for i in range(n):
if weights[i] <= w:
old_val = dp[w]
new_val = dp[w - weights[i]] + values[i]
if new_val > old_val:
dp[w] = new_val
print(f" w={w}: item {i} (w={weights[i]}, v={values[i]}) "
f"-> dp[{w}] = dp[{w-weights[i]}] + {values[i]} = {new_val}")
history.append(dp.copy())
print(f"\nFinal: {dp}")
return dp[capacity], history
# Walkthrough example
weights = [2, 3, 4]
values = [5, 8, 9]
capacity = 7
result, _ = unbounded_knapsack_dp_verbose(weights, values, capacity)
# Output shows how dp[7] = 17 is computed (items of weight 2+2+3 = values 5+5+8 = 18,
# or weight 2+2+2 = value 15, etc.)
Space-Optimized Implementation
The 1D solution is already space-optimized. The critical insight is loop order: we iterate forward through capacities. This differs from 0/1 knapsack, which requires backward iteration to prevent using the same item twice.
In unbounded knapsack, forward iteration is correct because we want dp[w - weight[i]] to potentially include item i already. That’s the whole point—unlimited usage.
from typing import List, Tuple, Dict
def unbounded_knapsack_with_reconstruction(
weights: List[int],
values: List[int],
capacity: int
) -> Tuple[int, Dict[int, int]]:
"""
Returns (max_value, item_counts) where item_counts[i] = number of item i taken.
"""
n = len(weights)
dp = [0] * (capacity + 1)
# Track which item was last added to achieve dp[w]
last_item = [-1] * (capacity + 1)
for w in range(1, capacity + 1):
for i in range(n):
if weights[i] <= w:
candidate = dp[w - weights[i]] + values[i]
if candidate > dp[w]:
dp[w] = candidate
last_item[w] = i
# Reconstruct solution by backtracking
item_counts = {i: 0 for i in range(n)}
remaining = capacity
while remaining > 0 and last_item[remaining] != -1:
item_idx = last_item[remaining]
item_counts[item_idx] += 1
remaining -= weights[item_idx]
return dp[capacity], item_counts
# Example usage
weights = [2, 3, 4]
values = [5, 8, 9]
capacity = 10
max_val, counts = unbounded_knapsack_with_reconstruction(weights, values, capacity)
print(f"Maximum value: {max_val}")
print(f"Items taken: {counts}")
# Output: Maximum value: 25, Items taken: {0: 5, 1: 0, 2: 0}
# (5 copies of item 0 with weight 2 and value 5)
Variations and Extensions
The unbounded knapsack pattern appears in many disguises. Recognizing these variations lets you apply the same solution template.
Coin Change (Minimum Coins): Given coin denominations, find minimum coins to make a target amount. This is unbounded knapsack minimizing count instead of maximizing value.
from typing import List
def min_coins(coins: List[int], amount: int) -> int:
"""
Minimum coins needed to make amount.
Returns -1 if impossible.
This is unbounded knapsack where:
- weights = coin denominations
- values = 1 (each coin costs 1 to use)
- goal = minimize total value (coin count)
"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # 0 coins needed for amount 0
for a in range(1, amount + 1):
for coin in coins:
if coin <= a and dp[a - coin] != float('inf'):
dp[a] = min(dp[a], dp[a - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
def coin_change_ways(coins: List[int], amount: int) -> int:
"""
Count number of ways to make amount.
Note: This requires different loop order to avoid counting permutations.
"""
dp = [0] * (amount + 1)
dp[0] = 1 # One way to make 0: use nothing
# Iterate coins first to count combinations, not permutations
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]
return dp[amount]
# Test
print(min_coins([1, 3, 4], 6)) # Output: 2 (3+3)
print(coin_change_ways([1, 2, 5], 5)) # Output: 4 ways
Rod Cutting: Given rod length n and prices for each length, find maximum revenue from cutting. Each length is an “item” with weight=length and value=price.
def rod_cutting(prices: List[int], length: int) -> int:
"""
prices[i] = price for rod of length i+1
"""
dp = [0] * (length + 1)
for l in range(1, length + 1):
for cut_len in range(1, l + 1):
if cut_len <= len(prices):
dp[l] = max(dp[l], dp[l - cut_len] + prices[cut_len - 1])
return dp[length]
Performance Comparison and Best Practices
Both memoization and tabulation achieve O(n × W) time complexity. In practice, tabulation typically performs better due to lower constant factors—no recursion overhead, better cache locality, and no hash table lookups.
| Approach | Time | Space | Best For |
|---|---|---|---|
| Recursive + Memo | O(nW) | O(W) + stack | Sparse subproblem access |
| Tabulation | O(nW) | O(W) | Dense problems, production code |
Common pitfalls:
-
Wrong loop order: Forward iteration for unbounded, backward for 0/1. Mixing these up produces incorrect results silently.
-
Zero-weight items: An item with weight 0 and positive value creates infinite loops or infinite value. Filter these out or handle explicitly.
-
Integer overflow: Large capacities and values can overflow. Use appropriate types or check bounds.
-
Confusing variations: Coin change counting combinations requires coins-first loop order. Counting permutations uses capacity-first. Know which you need.
Choose unbounded knapsack when items are fungible resources you can use repeatedly. Choose bounded (0/1) when items are unique or limited. When in doubt, the problem statement’s phrasing about “types” versus “items” usually indicates which variant applies.