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.

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.

Quote:

---

Originally Posted by math8

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

Quote:

---

Originally Posted by OReubens

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.

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.

Quote:

---

"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 :)

Quote:

---

Originally Posted by OReubens

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.