Question

Show that the greedy approach always finds an optimal solution for the Change problem when the coins are in the denominations d0, d1, d2,, ...,di for some integers i>0 and d>0

Answer 1

It is not guaranteed for a greedy algorithm to yield an optimal result in this case. Consider the case when we have the denomination as {1, 4, 5} and we have to find the change for 8.

Let's apply the greedy approach to the problem.

In the first step, greedy wi choose the highest possible value less than or equal to 8, i.e. 5,

remaining 8-5 = 3

Now, it will select the highest value greater less than or equal to 3, i.e. 1.

Remaining 3-1 = 2

Now, it will select the highest value greater less than or equal to 2, i.e. 1.

Remaining 2-1 = 1

Now, it will select the highest value greater less than or equal to 1, i.e. 1.

Remaining 1-1 = 0

Greedy, in this case, would result in {5, 1, 1, 1}, while the optima solution is {4, 4}.

However, if d0, d1, d. . . di happens to be the powers of a positive number greater than 1, then the greedy approach which yields an optimal solution.