CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 2 of 2 FirstFirst 12
Results 16 to 21 of 21
  1. #16
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,635

    Re: Coin/Money change code doesn't give exact change!

    It just looks overly convoluted. It would help to see what's going on if you used meaningful variable names. I thought the approach I was getting at in post 8 was substantially simpler.

  2. #17
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: Coin/Money change code doesn't give exact change!

    This is a typical "knapsack" problem.
    There is no easy generic answer, this is classified as NP-Hard.

    You can however make a solution that will fit the specific coinage you're having here and which will find the answer "reasonably fast" (well quite fast since the variance is quite low in this specific instance). a bruteforce or backtracking solution should do the trick.

    If you need to recalculate returns over and over, you may want to create a table that holds the "best fit" answers for all possible cents values.

  3. #18
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Coin/Money change code doesn't give exact change!

    Quote Originally Posted by math8 View Post
    hmmm, let see. Maybe something like:

    Code:
    for(int i=0; i<=n/10;i++)
    {
        if((n-(i*10))%25 ==0)
        {
                  x=i;             //number of 10's
                  z=(n-(i*10))/25 ; //number of 25's
                  break;
         }
    }
    No code.

    Pretend you don't know algebra, just basic arithmetic and common sense smarts.

    How would a lay-person attempt to solve the problem? Wouldn't the person try to take the most quarters they can, and then see if they can fill in the missing amount with just dimes?

    If they find out they can fill in the missing amount with dimes, fine. If they can't, then they will try again the same step but use less quarters and fill in the missing amount with dimes. Repeat with the "less quarters, fill with dimes" until done.

    That is basically GCDEF is stating, and why you don't need to know any C++, programming, computer science, or even algebra to come up with a solution.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; February 21st, 2013 at 12:53 PM.

  4. #19
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,635

    Re: Coin/Money change code doesn't give exact change!

    Quote Originally Posted by OReubens View Post
    This is a typical "knapsack" problem.
    There is no easy generic answer, this is classified as NP-Hard.

    You can however make a solution that will fit the specific coinage you're having here and which will find the answer "reasonably fast" (well quite fast since the variance is quite low in this specific instance). a bruteforce or backtracking solution should do the trick.

    If you need to recalculate returns over and over, you may want to create a table that holds the "best fit" answers for all possible cents values.
    His problem as stated is actually very simple to solve. Neither brute force, not backtracking is required. I can think of two simple solutions, but I'd kind of like the OP to come up with something on his own, or with gentle prodding, rather than spelling them out directly.

  5. #20
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: Coin/Money change code doesn't give exact change!

    This is simple, yes... if you want a general solution that will work for any coinage, it's NP-hard. (it's still semi-easy if you flip the problem sideways and have enough memory to hold a "table of every possible value up to the largest common denominator of all coins").

    The solution you propose in #8... is in fact a backtracking one.
    "Basically, if the number remaining after you take out the quarters isn't divisible by 10, you took out too many quarters."
    that sort of implies trying something, and when you find at the end you're stuck, you take a step back, apply a correction and try to continue again.
    You don't have to actually program it with a formal backtrack, but the methodology still is

  6. #21
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,635

    Re: Coin/Money change code doesn't give exact change!

    Quote Originally Posted by OReubens View Post
    This is simple, yes... if you want a general solution that will work for any coinage, it's NP-hard. (it's still semi-easy if you flip the problem sideways and have enough memory to hold a "table of every possible value up to the largest common denominator of all coins").

    The solution you propose in #8... is in fact a backtracking one.

    that sort of implies trying something, and when you find at the end you're stuck, you take a step back, apply a correction and try to continue again.
    You don't have to actually program it with a formal backtrack, but the methodology still is
    I don't agree. It's not backtracking in the classical sense, which is usually part of a brute force solution. The most you'll have to do is back out one quarter. You're not "trying to continue". Back out the quarter and it's guaranteed you can continue. You could test when calculating the quarters and eliminate that step if you want to anyway.

    As I said, I can think of two very simple approaches, that being one of them, the other involves starting by calculating the dimes first.

Page 2 of 2 FirstFirst 12

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