Unbounded Knapsack and Coin Change

Each item type infinite copies—inner loop forward on weight so later states reuse updated values in same round.

Why this shows up in the real world

Coin change fewest coins or ways to make amount. Cutting stock with reusable lengths.

Core idea (explained for students)

Forward loop for w from wt to W: dp[w]=max(dp[w],dp[w-wt]+val) distinguishes bounded (backward) vs unbounded.

Try this in Python

def unbounded_knapsack_max(W: int, weights: list[int], values: list[int]) -> int:
    dp = [0] * (W + 1)
    for wt, val in zip(weights, values):
        for w in range(wt, W + 1):
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]


print(unbounded_knapsack_max(10, [2, 3, 5], [15, 20, 30]))

Common mistakes

• Confusing bounded vs unbounded loop direction.
• Counting vs max—different recurrences.

Key takeaways

• Separate tables for counting with modulo vs maximizing value.