 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member Join Date
Apr 2014
Posts
5

## 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.)  Reply With Quote

2. ## Re: Greedy Alogrithm Help

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

3. Junior Member Join Date
Apr 2014
Posts
5

## Re: Greedy Alogrithm Help

hi,

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

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```
http://en.wikipedia.org/wiki/Greedy_algorithm  Reply With Quote

5. Elite Member Power Poster           Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

## 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.  Reply With Quote

6. Banned Join Date
Aug 2013
Posts
55

## 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.  Reply With Quote

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.  Reply With Quote

8. Junior Member Join Date
Apr 2014
Posts
5

## 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  Reply With Quote

9. Elite Member Power Poster           Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

## Re: Greedy Alogrithm Help

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

algorithms, greedy #### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• 