Dennis Shasha

Omniheurist Course

Computer Science



You are in charge of designing the denominations of coins. In the U.S., the denominations are penny, nickel, dime, quarter, half dollar, and dollar. Ignore the dollar coin for now. You have made a study and have determined that it is twice as likely for the subdollar portion of the price of an item to be a multiple of 5 cents than not. For example, 15 cents is twice as likely to be the price as 43 cents.

Hint: dynamic programming is a good start. A good solution for cost c can be built from solutions for smaller costs. The question is how to navigate the search space.