Mint
Dennis Shasha
Omniheurist Course
Computer Science
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 non5 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.