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

My coin/money change code works when there can be an exact change each time, i.e. when the 1 cent option is available. However, when the change options are only $10, $5, $1, 25 cents and 10 cents, it does not give me what I want for instance, I wanted to get change for $237.80, I was expecting to get:

23 10's, one 5, two 1's and 8 dimes. However, the code below is giving me 23 10's, one 5, two 1's and 3 quarters (there is no option left for the 5 remaining cents).

Any idea on how to fix it?

Code:

---

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

void change(double cents, int a[]);

int main()
{
    double Dollars;
    double cents;
  // int a[]={25,10,5,1}; denominations of coins, could have been any numbers in DECREASING order.
    int a[]={1000,500,100,25,10};
   
    cout<<"Please enter an amount in the format $x.xx: ";
    cin>> Dollars;
   
    cents=100*Dollars;
   
   
    cout<<endl<<Dollars<<" dollars is equal to "<<cents<<" cents"<<endl<<endl;
    change(cents, a);
   
   
cin.get();
std::cout << "Press ENTER to continue...";
std::cin.ignore( std::numeric_limits<std::streamsize>::max(), '\n' ); 
}

void change(double cents, int a[]){
    int money=cents;
    double coins[4];
    cout<<"The change is  respectively [";
    for(int i=0;i<5;i++){
            double remainder=money%a[i];
            coins[i]=(money-remainder)/a[i];
            money=remainder;
            cout<<coins[i]<<" ";
            }
            //cout<<"] quarters, dimes, nickels and pennies."<<endl<<endl;
            cout<<"] 10's, 5's, 1's, quarters and dimes."<<endl<<endl;
       
           
}

---

Shouldn't it give you two quarters and three dimes?

yeah, it should, my bad. Unfortunately, it doesn't.

The first thing to do is figure out the rules for the algorithm using a pencil and paper. Figure out the logic then worry about the code.

What debugging have you done? You don't mention this. If the code doesn't perform as per the design then you need to debug the code. If the code is performing as per the design, then the design needs modifying and the code updated to reflect the new design.

- design
- code
- test
- debug

Quote:

---

Originally Posted by 2kaud

What debugging have you done? You don't mention this. If the code doesn't perform as per the design then you need to debug the code. If the code is performing as per the design, then the design needs modifying and the code updated to reflect the new design.

- design
- code
- test
- debug

---

You can look at his code and see that algorithm isn't correct. That's why I said he needs to actually figure out how he's going to approach it before he tries to code it.

I think the code is performing how it should, I think the problem is behind the logic (I guess that's the design). I am hoping to get 23 10's, one 5, two 1's ,2 quarters and 3 dimes.

The logic that I had was to use as many higher denominations in an effort to use the least number of coins. Let say, all denominations were available, then by using this logic, I would have at the end(for the cents), 3 quarters and 1 nickel, (i.e. 4 coins total), as opposed to 2 quarters and 3 dimes (5 coins total). However, in this case, it doesn't work since nickels and pennies aren't available.

I am not sure in which direction I should go.

Quote:

---

Originally Posted by math8

I think the code is performing how it should, I think the problem is behind the logic (I guess that's the design). I am hoping to get 23 10's, one 5, two 1's ,2 quarters and 3 dimes.

The logic that I had was to use as many higher denominations in an effort to use the least number of coins. Let say, all denominations were available, then by using this logic, I would have at the end(for the cents), 3 quarters and 1 nickel, (i.e. 4 coins total), as opposed to 2 quarters and 3 dimes (5 coins total). However, in this case, it doesn't work since nickels and pennies aren't available.

I am not sure in which direction I should go.

---

As I said, stop thinking in terms of programming and start thinking in terms of logic. Basically, if the number remaining after you take out the quarters isn't divisible by 10, you took out too many quarters.

Quote:

---

Originally Posted by math8

I think the code is performing how it should, I think the problem is behind the logic (I guess that's the design). I am hoping to get 23 10's, one 5, two 1's ,2 quarters and 3 dimes.

---

You're wasting time thinking about the dollars. That is simple and can be done by "greedy" logic -- take as many 10's, 5's and 1's to make the dollar total.

You should concentrate on the cents value. Given a cents value, can you divide it evenly into 25 cent and 10 cent portions? And if so, how would you do it? And you don't need C++ code to figure it out, as this is a general logic question.

Regards,

Paul McKenzie

when you say "evenly" do you mean by solving: 25x+10x=y, where y is the cents value?

Quote:

---

Originally Posted by math8

when you say "evenly" do you mean by solving: 25x+10x=y, where y is the cents value?

---

You have an unlimited number of quarters and dimes to grab from a pot. You have to make a total value of n cents. Can you take those quarters and dimes and create n cents with it? If so, how would you do it in a logical, consistent manner? Included in this solution is the "I can't do it" result, meaning that n can't be broken down into quarters and dimes evenly.

Forget about algebra for the moment -- write it out on paper if you have to and figure out a way of doing this. It is simply stated, so I don't know how much more simpler the problem can be presented.

Anyway, how was your formula going to work? The number of dimes and number of quarters are not necessarily the same value, yet you represented them both with "x".

Regards,

Paul McKenzie

I wasn't sure what you meant by "evenly". But first of, intuitively, for this problem to make sense , the "cents part" n must be either 0 or >=10 and at least n must be a multiple of 5 .
So the only "logic thing" I can think of doing, is to check if n is divisible by 25, if not, take n-10 and see whether it is divisible by 25, if not, then take n-20 and check whether it is is divisible by 25, etc..

In other words, I would solve:
minimize x
such that n-(x*10) modulo 25 = 0.
x non-negative integer.

x: would be the number of 10's;
z=[n-(x*10) ]/25 would be the number of 25's.

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;
    }
}

---

You're overthinking it. Read what I said in post #8.

alright, but aside from that, what is wrong with what I wrote before?

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.