Programming Praxis

[ Today’s exercise was contributed by Tom Rusting, who worked as a programmer until the mid 70’s. Being retired, he has now taken up programming again as a hobby. Suggestions for exercises are always welcome, or you may wish to contribute your own exercise; feel free to contact me if you are interested.

Floup is an island-country in the South Pacific with a currency known as the floupia; coins are denominated in units of 1, 3, 7, 31 and 153 floupias. Merchants and customers engage in a curious transaction when it comes time to pay the bill; they exchange the smallest number of coins necessary to complete the payment. For instance, to pay a bill of 17 floupia, a customer could pay three 7-floupia coins and receive single 1-floupia and 3-floupia coins in exchange, a total of five coins, but it is more efficient for the customer to pay a single 31-floupia coin and receive two 7-floupia coins in exchange.

Your task is to write a program that determines the most efficient set of coins needed to make a payment, generalized for any set of coins, not just the set 1, 3, 7, 31 and 153 described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2