CODEWITHSUNDEEP
javaalgorithmmathgreedycs50
Mr Chasi
Mr Chasi

Reputation: 437

Greedy Algorithm Giving Dubious Results

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

Upvotes: 0

Views: 161

Answers (3)

FredK
FredK

Reputation: 4084

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.

Upvotes: 0

GavinCattell
GavinCattell

Reputation: 3963

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

Upvotes: 2

Amit
Amit

Reputation: 46323

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

Upvotes: 1

Related Questions