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

GavinCattell GavinCattell · Accepted Answer · 2016-09-17T19:53:10

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

Greedy Algorithm Giving Dubious Results

Results:

3 Answers