Re: Greedy Alogrithm Help

No.

Try to "change" 35c using the coins of nominal 10c, 7c and 1c.

Re: Greedy Alogrithm Help

hi,

so how did u get the 35c. i don't understand that part?

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

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.

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.

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.

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

Re: Greedy Alogrithm Help

neither of those 2 solutions for 5 coins are obtained usign the greedy algorithm.