Printable View
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.)
No.
Try to "change" 35c using the coins of nominal 10c, 7c and 1c.
hi,
so how did u get the 35c. i don't understand that part?
using Greedy Alogrithm:Optimal:Code:3 x 10c +5 x 1c
total coins: 3 + 5 = 8
See also:Code:2 x 10c + 2 x 7c + 1 x 1c
total coins: 2 + 2 + 1 = 5
http://en.wikipedia.org/wiki/Greedy_algorithm
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.
Not that it matters for the point you've made but there's yet another optimal solution:Quote:
Originally Posted by VictorN;
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.Quote:
Originally Posted by zizz
Not that it matters for the point you've made but there's yet another optimal solution:Quote:
Originally Posted by VictorN
5 x 7c = 35c
which also has 5 coins.
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
neither of those 2 solutions for 5 coins are obtained usign the greedy algorithm.