Description

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.

• Your first job is to design a set of 5 coin denominations such that the expected number of coins required to give exact change for a purchase is minimized given these constraints. This is called the Exact Change Number. Using the U.S. denominations, the Exact Change Number for 43 cents can be realized by one quarter, one dime, one nickel, and three pennies, thus giving a total of 6.
• Let the Exchange Number of a purchase be the number of coins given from the buyer to the seller plus the number given in change to the buyer from the seller. For an item costing 43 cents using the U.S. denominations, the Exchange Number can be realized by having the buyer pay 50 cents and receiving a nickel and two pennies in return, giving a total of only 4. You can assume the availability of 1 dollar. So, the Exchange Number for 99 cents is 1 since a penny is returned after handing the seller 1 dollar. Your second job is to design a set of 5 coin denominations such that the Exchange Number of coins required for a purchase is minimized given these constraints.
• For both jobs, please print out the average number of coins passed around and give me the number for each coin.

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.