Recall the problem of us having coins of denominations d_1, d_2, ..., d_n and we

Question

Recall the problem of us having coins of denominations d_1, d_2, ..., d_n and we want to make change for T cents. We have an unlimited supply of each coin, and want to know the fewest number of coins that add up to T, if possible. In class we looked at the subproblem C [t] as being the minimum number of coins to make change for t lessthanorequalto T cents (C[t] = infinity means it is not possible). We also derived a recurrence relation for C: C[t] = {infinity if t

Explanation / Answer

cents = 200 denominations = [25, 10, 5, 1] names = {25: "quarter(s)", 10: "dime(s)", 5 : "nickel(s)", 1 : "pennies"} def count_combs(left, i, comb, add): if add: comb.append(add) if left == 0 or (i+1) == len(denominations): if (i+1) == len(denominations) and left > 0: comb.append( (left, denominations[i]) ) i += 1 while i

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

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