
April 29th, 2014, 11:21 AM
#1
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, 12:05 PM
#2
Re: Greedy Alogrithm Help
No.
Try to "change" 35c using the coins of nominal 10c, 7c and 1c.
Victor Nijegorodov

April 29th, 2014, 12:59 PM
#3
Re: Greedy Alogrithm Help
hi,
so how did u get the 35c. i don't understand that part?

April 29th, 2014, 01:07 PM
#4
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
See also:
http://en.wikipedia.org/wiki/Greedy_algorithm
Victor Nijegorodov

April 30th, 2014, 07:37 AM
#5
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, 09:48 AM
#6
Re: Greedy Alogrithm Help
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, 10:07 AM
#7
Re: Greedy Alogrithm Help
Originally Posted by zizz
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.
Victor Nijegorodov

May 1st, 2014, 03:02 PM
#8
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, 03:22 PM
#9
Re: Greedy Alogrithm Help
neither of those 2 solutions for 5 coins are obtained usign the greedy algorithm.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
