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

#### Hybrid View

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.)

2. ## Re: Greedy Alogrithm Help

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

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?

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

5. 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.

6. ## 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.

7. 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

8. 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.

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.

#### Posting Permissions

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