- Thread starter
- #1

- Apr 14, 2013

- 4,145

At the cash register of a store we want to give change of worth $V$ cents of euro. Create and analyze a greedy algorithm that gives the change using the minimum number of coins.

Assume that the available coins are the euro subdivisions, i.e. $\{1, 2, 5, 10, 20, 50\}$ and that we have an unlimited number of coins for each subdivision.

For this question I have done the following pseudocode:

Code:

```
Algorithm min_number_coins (C, V)
Input: array C={1,2,5,10,20,50} in ascending order and given value V
Output: array A with minum number of coins
A <- ∅
for i <- 5 downto 0 do
while V >= C[i] do
A <- A U C[i]
V <- V - C[i]
if V = 0 then
return A
```

For the complexity: In the worst case we need $V$ coins for the change, if we have only the subdivision $1$. So the complexity of the for-loop and so also of the algorithm is $O(V)$, right?

Now I am asked the following:

Generalizing the above problem, we have the set of different coins $\{c_0, c_1,\ldots , c_n\}$ with $c_0 <c_1 <\ldots <c_n$ from which we want to give the change of value $V$ using the minimum number of coins. We consider that $c_0 = 1$.

Create and analyze a dynamic programming algorithm that finds an optimal solution to the problem, commenting on both time and space complexity of the algorithm.

Could you explain to me the idea how we use the dynamic programming here? I mean the recurrence relation that we have to use. I haven't really undersood that.