CODEWITHSUNDEEP
c++algorithmfloating-pointcurrency
keeda
keeda

Reputation: 2635

Count number of ways to make an amount with change given

I was trying to code an algorithm to count the number of different possible ways the make a certain amount with the given denominations. Assume the US dollar is available in denominations of $100, $50, $20, $10, $5, $1, $0.25, $0.10, $0.05 and $0.01. Below function, works great for int amount and int denominations 

/* Count number of ways of making different combination */
int Count_Num_Ways(double amt, int numDenom, double S[]){
   cout << amt << endl; //getchar();

  /* combination leads to the amount */
  if(amt == 0.00)
    return 1;

  /* No combination can lead to negative sum*/
  if(amt < 0.00)
    return 0;

  /* All denominations have been exhausted and we have not reached
     the required sum */
  if(numDenom < 0 && amt >= 0.00)
    return 0;

  /* either we pick this denomination, this causes a reduction of 
     picked denomination from the sum for further subproblem, or 
     we choose to not pick this denomination and 
     try a different denomination */
   return Count_Num_Ways(amt, numDenom - 1, S) + 
          Count_Num_Ways(amt - S[numDenom], numDenom, S);
}

but when I change my logic from int to float, it goes into infinite loop. I suspect that it is because of floating point comparisons in the code. I am not able to figure out the exact cause for a infinite loop behavior. Any help in this regard would be helpful.

Upvotes: 3

Views: 3320

Answers (2)

arne
arne

Reputation: 4674

floating point operations cannot be exact, because of the finite representation. This way you will never ever end up with exactly 0.0. That's why you always test an interval like so:

if (fabs(amt - 0.0) < TOL)

with a given tolerance of TOL. TOL is chosen appropriately for the application, in this case, 1/2 cent should already be fine.

EDIT: Of course, for this kind of thing, Daemin's answer is much more suitable.

Upvotes: 4

Dominik Grabiec
Dominik Grabiec

Reputation: 10655

When dealing with such "small" currency amounts and not dealing with interest it will be much easier to just deal with cents and integer amounts only, not using floating point.

So just change your formula to use cents rather than dollars and keep using integers. Then when you need to display the amounts just divide them by 100 to get the dollars and modulo 100 to get the cents.

Upvotes: 8

Related Questions