-
April 29th, 2014, 10: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, 11:05 AM
#2
Re: Greedy Alogrithm Help
No.
Try to "change" 35c using the coins of nominal 10c, 7c and 1c.
Victor Nijegorodov
-
April 29th, 2014, 11:59 AM
#3
Re: Greedy Alogrithm Help
hi,
so how did u get the 35c. i don't understand that part?
-
April 29th, 2014, 12: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, 06: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, 08: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, 09: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, 02: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, 02: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
|