Greedy Algorithm Giving Dubious Results

Question

I am implementing a simple greedy algorithm:

Aim: To pay-back the user's change using as few coins as possible out of the following coin types; Quarter (0.25), Dime (0.10), Nickel (0.05) & Penny (0.01).

Input: The amount of change the user is owed.

Output: The total number of coins used in paying-back the user.

A snippet of my code can be seen below:

final double quarter = 0.25d;
final double dime = 0.10d;
final double nickel = 0.05d;
final double penny = 0.01d;
double changeOwed;
int coinsUsed = 0;

/*
Code to get the user's input
*/

    while (changeOwed > 0 && changeOwed % quarter != changeOwed) {
        coinsUsed++;
        changeOwed -= quarter;
    }

    while (changeOwed > 0 && changeOwed % dime != changeOwed) {
        coinsUsed++;
        changeOwed -= dime;
    }

    while (changeOwed > 0 && changeOwed % nickel != changeOwed) {
        coinsUsed++;
        changeOwed -= nickel;
    }

    while (changeOwed > 0 && changeOwed % penny != changeOwed) {
        coinsUsed++;
        changeOwed -= penny;
    }

    System.out.println("Change remaining: "+ changeOwed);
    System.out.println("Total coins used: "+coinsUsed);

Results:

Enter change owed: 32
Change remaining: 0.0
Total coins used: 128

Enter change owed: 3.25
Change remaining: 0.0
Total coins used: 13

Enter change owed: 0.32
Change remaining: 3.469446951953614E-18
Total coins used: 4

I decided to do this using while loops, and the modulo operator. If changeOwed were equal to 0, then there would be no need to execute the while loop, because all of the change would've been paid-back. To add to this, if changeOwed % COINTYPE ("COINTYPE" being an arbitrary placeholder) were equal to changeOwed, this would indicate that COINTYPE is greater than changeOwed (the amount of remaining change). In such an event, the program proceeds to he next while-loop sporting a smaller COINTYPE.

As can be seen above, the algorithm seems to produce the correct output as regards the amount of coins used. However, as in the last example, the amount of change remaining seems to be way off. I understand that computers cannot do perfect arithmetic due to a finite number of bits. However, why is it that the amount of change remaining has increased drastically from 0.32 to 3+?

In general, for money calculations it is better to use BigDecimal. — ACV
– ACV, Commented Sep 17, 2016 at 19:53
Wouldn't changeOwed % quarter != changeOwed be better written as changeOwed >= quarter. It's clearer on intent, and runs faster (no division). It will also fix the rounding issue you're having. — Andreas
– Andreas, Commented Sep 17, 2016 at 20:12

GavinCattell · Accepted Answer · 2016-09-17 19:53:10Z

2

It's not 3. Its 3E-18 which is a very small number (0. 18-zeros 3).

This is probably caused by using doubles. It's a floating point error.

If you want to avoid this use BigDecimal

answered Sep 17, 2016 at 19:53

GavinCattell

4,01323 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Amit · Accepted Answer · 2016-09-17 19:52:58Z

1

3.469446951953614E-18 is a very small number. It is not the scale of 3.0.

answered Sep 17, 2016 at 19:52

Amit

46.5k9 gold badges84 silver badges114 bronze badges

2 Comments

Mr Chasi Over a year ago

Oh, I see... I feel silly now haha. So is it so that the algorithm itself actually correct? The problem lies solely with floating-point arithmetic?

Amit Over a year ago

I actually didn't read the algorithm, I concentrated on your description of the problem... What I can say is, this problem doesn't require any loops, simple arithmetic will do just fine.

FredK · Accepted Answer · 2016-09-17 20:03:14Z

0

Since you are talking about coins and change, there is no need to use real numbers here. Instead of BigDecimal, you can just use long, and compute everything in the number of cents, not the number of dollars.

answered Sep 17, 2016 at 20:03

FredK

4,1141 gold badge11 silver badges11 bronze badges

Collectives™ on Stack Overflow

Greedy Algorithm Giving Dubious Results

Results:

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Results:

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related