Unbounded Knapsack

Foundations

So far, each slot chose between at most two earlier slots. Now, what if every slot has many choices, one per item you could use last, and each item may be used again and again?

The unbounded knapsack pattern indexes the table by the total still to be made. Let fewest[t] be the fewest items that add up to exactly t, with fewest[0] = 0. Whatever item v comes last, the rest must make t - v as cheaply as possible, so fewest[t] = 1 + min(fewest[t - v]) over every item v <= t. Totals no item can reach stay at infinity.

Make 11 from values of nums = [7, 1, 5, 3, 6], each usable any number of times, with as few values as possible. Filling totals 0 to 11 gives fewest[11] = 2: ending with 5 reads fewest[6] = 1, and ending with 6 reads fewest[5] = 1. Grabbing the largest value first would take 7, then 3, then 1, three values, which is why every last choice is tried.

Case Scenario

Coin Change is the unbounded knapsack with coins for items: each coin can be used any number of times, and dp[a] is the fewest coins that make amount a, or infinity if none can. The answer is dp[amount], or -1 if it stays infinite. For coins = [1, 3, 4] and amount = 6, the answer is 2, from 3 + 3, while taking the biggest coin first gives 4 + 1 + 1.

The direct approach tries every coin as the last one and recurses on what is left. The same remainders, such as 3, are solved again and again along different paths, so the work grows exponentially with the amount. The tempting shortcut, always taking the biggest coin that fits, is fast but wrong: for 6 it picks 4 + 1 + 1.