CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9
  1. #1
    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. #2
    VictorN's Avatar
    VictorN is online now Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Hanover Germany
    Posts
    20,396

    Re: Greedy Alogrithm Help

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

  3. #3
    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. #4
    VictorN's Avatar
    VictorN is online now Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Hanover Germany
    Posts
    20,396

    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

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

  6. #6
    Join Date
    Aug 2013
    Posts
    55

    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.

  7. #7
    VictorN's Avatar
    VictorN is online now Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Hanover Germany
    Posts
    20,396

    Re: Greedy Alogrithm Help

    Quote Originally Posted by zizz View Post
    Quote Originally Posted by VictorN View Post
    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

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

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

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
  •  





Click Here to Expand Forum to Full Width

Featured