Unbounded Knapsack and Coin Change

Same knapsack, new rule: you may take item i as many times as capacity allows. Coins are the usual contest costume — denominations coins[j], make amount A, unlimited supply of each coin.

Two scores:

- Max value unbounded knapsack (the 0/1 table with the inner loop reversed). - Min coins (LeetCode Coin Change): dp[x] = fewest coins summing to x, or impossible.

The second one is what you will code in the arena. Greedy (always the largest coin) is wrong as soon as denominations are ugly: coins 1, 3, 4 and amount 6 — greedy takes 4+1+1 (3 coins); two threes is 2.

Min coins, unbounded. dp[x] = min over coin c of dp[x - c] + 1js

function coinChange(coins, amount) {
  const inf = amount + 1;
  const dp = Array(amount + 1).fill(inf);
  dp[0] = 0;
  for (let x = 1; x <= amount; x++) {
    for (const c of coins) {
      if (c <= x) dp[x] = Math.min(dp[x], dp[x - c] + 1);
    }
  }
  return dp[amount] >= inf ? -1 : dp[amount];
}

TRACE

coins = [1, 3, 4], amount = 6. Fill min-coin dp[0..6]. Use 7 as 'impossible' sentinel.

Base

dp[0] = 0. Everything else 7 (amount+1).

dp = [0, 7, 7, 7, 7, 7, 7]

1 / 6

CHECK

coins = [1, 3, 4], amount = 6. Greedy largest-first uses 4+1+1. What does the DP return, and why is greedy legal on US coins but not here?

dp[0] = 0 (zero coins make zero). Unreachable amounts stay at the sentinel; return -1 if dp[amount] never dropped. Order of coins does not matter for correctness of this complete-inner-loop form.

A related problem is combination count (number of ways). Then the *outer* loop must be the coins, so [1,2] and [2,1] are not double-counted as different ways — unless the statement wants permutations. Read the statement. Min-coins does not care about order.

CHECK

You copy the 0/1 rolling loop (c from W down to wt) for unbounded knapsack. What happens?

Checks 0/2

Next lesson