Bioinformatics Algorithms/

...

/

Changing Money Recursively

Changing Money Recursively

Let’s look at a recursive solution to the Change Problem.

We'll cover the following...

Since the greedy solution used by Roman cashiers to solve the Change Problem is incorrect, we’ll consider a different approach. Suppose you need to change 76 denarii, and you only have coins of the three smallest denominations: Coins = (5, 4, 1). A minimal collection of coins totaling 76 denarii must be one of the following:

  • a minimal collection of coins totaling 75 denarii, plus one 1-denarius coin;

  • a minimal collection of coins totaling 72 denarii, plus one 4-denarius coin;

  • a minimal collection of coins totaling 71 denarii, plus one ...