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 four times 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 four times as likely to be the price as 43 cents. But any 5 cent multiple is equally likely as any other 5 cent multiple and ditto for the non-5 cent multiples.

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.