Dynamic programming: which recurrence relation do we use?

[mathmari]

Hey! :unsure:

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:

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

Is that correct? At the for loop is it correct to take $i$ from $5$ or do I have to set a new variable n = length(C) ? :unsure:

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? :unsure: 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. :unsure:

 

[mathmari]

For the dynamic programming I have found the below code:

So we calculate for eacj $j$ between $1$ and $V$ the set with the minimum number of coins to get the value $j$, right? :unsure:

 

[I like Serena]

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
...

Is that correct? At the for loop is it correct to take $i$ from $5$ or do I have to set a new variable n = length(C) ?

Hey mathmari!

The use of 5 would be fine if C were a local constant. But it's not. Instead it's an input and the input specification does not say that it is of size 5.
So it is indeed better to use length(C) instead of 5. There is no need to introduce a new variable n for it though.
Do note that length(C) is 6 and not 5.

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?

Well, we have C as input, and it is not given that it only has the subdivision $1$.
And with the given C and algorithm, we will only have a maximum of 4 cents.
However, given the largest coin c, it will take $\lfloor V / c\rfloor$ iterations to find the number of coins $c$. Beyond that we have a fixed worst case number of iterations to divide the remainder. So the complexity is indeed $O(V)$.

Btw, we can also output an array with the numbers of each coin, couldn't we?
Then we could use $A[ i ] \leftarrow A[ i ] + 1$.

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 understood that.

I guess we could make the algorithm recursive.
That is, we can find how many times the largest coin fits and make a recursive call to divide the remainder with the set of coins that excludes that largest coin.

For the dynamic programming I have found the below code:

View attachment 10840So we calculate for eacj $j$ between $1$ and $V$ the set with the minimum number of coins to get the value $j$, right?

What are $d$, $k$, $n$, $C$, and $S$?

And how is this a dynamic programming solution?
Doesn't dynamic programming imply that the problem is broken into smaller sub problems in a recursive fashion?