design a dynamic programming algorithm for the change-making problem: given an a

Question

design a dynamic programming algorithm for the change-making problem: given an amount n and unlimited quantities of coins of each of the denominations d1, d2, …dm, find the smallest number of coins that add up to n or justify that the problem does not have a solution

Explanation / Answer

public final class MakeChange { // Dynamic programming algorithm to solve change making problem. // As a result, the coinsUsed array is filled with the // minimum number of coins needed for change from 0 -> maxChange // and lastCoin contains one of the coins needed to make the change. public static void makeChange( int [ ] coins, int differentCoins, int maxChange, int [ ] coinsUsed, int [ ] lastCoin ) { coinsUsed[ 0 ] = 0; lastCoin[ 0 ] = 1; for( int cents = 1; cents

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.