COEN 179 Lecture Notes - Lecture 14: Dime (United States Coin)

• School: Santa Clara University
• Department: Computer Engineering
• Course: COEN 179
• Professor: Tran

Document Summary

First thing to try if given problem is an optimization problem. (maximize/minimize some quantity). Idea: apply decrease-conquer strategy by selecting a choice that optimizes some criterion in each step. In other words, we make a sequence of local optimal decisions to obtain optimal decision. Input: a nonnegative amount n >= 0 (in cents) to make change for. Output: a smallest multi set of coins whose sum is n of denominations 1, 5, 10, 25 e. g. n = 43, the smallest set is {25, 10, 5, 1, 1, 1} > 6 coins. N = 30, the smallest set is {25, 5} 4 ways to reduce n: -25, -10, -5, -1 pick the choice that yields the largest reduction (pick largest denominations <= n) D = {25, 10, 5, 1}; //denominator in reverse sorted order for(i = 0; i < 4; ++i){ if(d[i] <= n) //largest denominator <= n return {d[i]) union cc(n - d[i]);