# Greedy Alogrithm Help

• April 29th, 2014, 10:21 AM
sls98
Greedy Alogrithm Help
Does the greedy algorithm always give an optimal solution in the system of denominations d(1) = 1, d(2) = 7, d(3) = 10? Justify answer. (If you say yes, prove it; if you say no, give a counter example to show that the greedy algorithm does not give an optimal solution.)
• April 29th, 2014, 11:05 AM
VictorN
Re: Greedy Alogrithm Help
No.
Try to "change" 35c using the coins of nominal 10c, 7c and 1c.
• April 29th, 2014, 11:59 AM
sls98
Re: Greedy Alogrithm Help
hi,

so how did u get the 35c. i don't understand that part?
• April 29th, 2014, 12:07 PM
VictorN
Re: Greedy Alogrithm Help
using Greedy Alogrithm:
Code:

```3 x 10c +5 x 1c total coins: 3 + 5 = 8```
Optimal:
Code:

```2 x 10c + 2 x 7c + 1 x 1c total coins: 2 + 2 + 1 = 5```
http://en.wikipedia.org/wiki/Greedy_algorithm
• April 30th, 2014, 06:37 AM
OReubens
Re: Greedy Alogrithm Help
Note that in most countries the available coins have been purposefully designed around values that will make a greedy algorithm always return an optimal solution.

There is no country that uses the "optimal" coinage to make all values between 0 and 100 possible with the lowest possible amount of different coins, because they're so irregular it's impractical for humans to work with.
• April 30th, 2014, 08:48 AM
zizz
Re: Greedy Alogrithm Help
Quote:

Originally Posted by VictorN;
Optimal:2 x 10c + 2 x 7c + 1 x 1c
total coins: 2 + 2 + 1 = 5

Not that it matters for the point you've made but there's yet another optimal solution:

5 x 7c = 35c

which also has 5 coins.
• April 30th, 2014, 09:07 AM
VictorN
Re: Greedy Alogrithm Help
Quote:

Originally Posted by zizz
Quote:

Originally Posted by VictorN
Optimal:
Code:

```2 x 10c + 2 x 7c + 1 x 1c total coins: 2 + 2 + 1 = 5```

Not that it matters for the point you've made but there's yet another optimal solution:
5 x 7c = 35c
which also has 5 coins.

Correct! There may be more than one different solutions for that task (in your OP), although neither of them can be obtained using Greedy Algorithm.
• May 1st, 2014, 02:02 PM
sls98
Re: Greedy Alogrithm Help
so if i am confused now , so in the question it asks Does the greedy algorithm always give an optimal solution in the system of denominations d(1) = 1, d(2) = 7, d(3) = 10 and the answer provided was no, and a counterexample was 3 x 10c +5 x 1c total coins: 3 + 5 = 8. Bu if the answer is no then how can there be a optimal solution? could you please help me understand
• May 1st, 2014, 02:22 PM
OReubens
Re: Greedy Alogrithm Help
neither of those 2 solutions for 5 coins are obtained usign the greedy algorithm.