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 N 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 might be 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. The N will be given in class and your programs will have 2 minutes to solve each of the following two problems. (N will be 1 or greater but may not be an integer.)

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.