0

So I was making this fairly straight forward optimal change program that works perfectly fine in most cases. But for some odd reason it acts inconsistent and sometimes won't add the last penny needed, but other times it will.

I've tried different outputs and the code always comes out correct except sometimes for the last penny; when using American currency. I'm sure the reason is obvious, but I just don't see it.

   public static int[] optimal_change(double[] currency, double amount) {

        int[] count = new int[currency.length];

        for (int i = 0; i < currency.length; i++) {
            if (amount >= currency[i]) {
                amount -= currency[i];
                count[i]++;
                i--;
            }
            if (amount == 0.0000) {
                break;
            }
        }

        return count;
    }

public static void main(String[] args) {

        double[] american_currency = {100,50,20,10,5,1,0.25,0.10,0.05,0.01};
        //Japanese currency: https://www.boj.or.jp/en/note_tfjgs/note/valid/index.htm/
        double[] japanese_currency = {10000,5000,2000,1000,500,100,50,10,5,1};

        int[] american_change = optimal_change(american_currency, 78.36);
        int[] japanese_change = optimal_change(japanese_currency, 793048);

        System.out.println("Optimal change for: $78.38");
        for (int i = 0; i < american_currency.length; i++) {
            if (i <= 5) {
                System.out.println(Integer.toString(american_change[i]) + " $" + Double.toString(american_currency[i]));
            } else {
                System.out.println(Integer.toString(american_change[i]) + " " + Double.toString(american_currency[i]) + "¢");
            }
        }
        System.out.println("--------------------------");
        System.out.println("Optimal change for: ¥793040");
        for (int i = 0; i < japanese_currency.length; i++) {

            System.out.println(Integer.toString(japanese_change[i]) + " ¥" + Double.toString(japanese_currency[i]));

        }


    }

Correct Results:

input: 78.37

output:

Optimal change for: $78.37

0 $100.0

1 $50.0

1 $20.0

0 $10.0

1 $5.0

3 $1.0

1 0.25¢

1 0.1¢

0 0.05¢

2 0.01¢

Incorrect Results:

input: 78.38

output:

Optimal change for: $78.38

0 $100.0

1 $50.0

1 $20.0

0 $10.0

1 $5.0

3 $1.0

1 0.25¢

1 0.1¢

0 0.05¢

2 0.01¢

The output Should have been:

Optimal change for: $78.38

0 $100.0

1 $50.0

1 $20.0

0 $10.0

1 $5.0

3 $1.0

1 0.25¢

1 0.1¢

0 0.05¢

3 0.01¢

Improve this question
2
  • 1
    Don’t use doubles when an exact answer is required. See chapter "Avoid float and double if exact answers are required" in "Effective Java". (item 48 here: the-eye.eu/public/Books/IT%20Various/…) Commented Apr 17, 2019 at 7:23
  • 1
    I strongly suspect this is because you are using double to represent currency. That has significant problems, because currency is naturally decimal, and not all decimal values can be exactly represented in binary floating point. For example, the value 0.1 can't be represented exactly. Options: 1) use integers, representing the number of cents (etc) rather than dollars. 2) use BigDecimal which is a decimal-based floating point type. Commented Apr 17, 2019 at 7:23

2 Answers 2

Reset to default
0

Switching To BigDecimal seemed to fix the issue. Not sure why the issue with doubles has persisted this long. But thankfully it works. 

import java.math.BigDecimal;

public class Greedy_Money_BigInteger {
    public static int[] optimal_change(BigDecimal[] currency, BigDecimal amount) {

        int[] count = new int[currency.length];

        for (int i = 0; i < currency.length; i++) {
            //if (amount >= currency[i]) {
            if (amount.compareTo(currency[i]) >= 0) {
                amount = amount.subtract(currency[i]);
                count[i]++;
                i--;
            }
            if (amount.compareTo(BigDecimal.valueOf(0)) <= 0) {
                break;
            }
        }

        return count;
    }


    public static void main(String[] args) {

        BigDecimal[] american_currency = {BigDecimal.valueOf(100),BigDecimal.valueOf(50),BigDecimal.valueOf(20),BigDecimal.valueOf(10),BigDecimal.valueOf(5),BigDecimal.valueOf(1),BigDecimal.valueOf(0.25),BigDecimal.valueOf(0.10),BigDecimal.valueOf(0.05),BigDecimal.valueOf(0.01)};
        //Japanese currency: https://www.boj.or.jp/en/note_tfjgs/note/valid/index.htm/
        BigDecimal[] japanese_currency = {BigDecimal.valueOf(10000),BigDecimal.valueOf(5000),BigDecimal.valueOf(2000),BigDecimal.valueOf(1000),BigDecimal.valueOf(500),BigDecimal.valueOf(100),BigDecimal.valueOf(50),BigDecimal.valueOf(10),BigDecimal.valueOf(5),BigDecimal.valueOf(1)};

        BigDecimal american_change_value = BigDecimal.valueOf(78.31);
        BigDecimal japanese_change_value = BigDecimal.valueOf(793043);

        int[] american_change = optimal_change(american_currency, american_change_value);
        int[] japanese_change = optimal_change(japanese_currency, japanese_change_value);

        System.out.println("Optimal change for: $" + american_change_value.toString());
        for (int i = 0; i < american_currency.length; i++) {
            if (american_change[i] > 0) {
                if (i <= 5) {
                    System.out.println(Integer.toString(american_change[i]) + " $" + american_currency[i].toString());
                } else {
                    System.out.println(Integer.toString(american_change[i]) + " " + american_currency[i].toString() + "¢");
                }
            }
        }
        System.out.println("--------------------------");
        System.out.println("Optimal change for: ¥" + japanese_change_value.toString());
        for (int i = 0; i < japanese_currency.length; i++) {
            if (japanese_change[i] > 0) {
                System.out.println(Integer.toString(japanese_change[i]) + " ¥" + japanese_currency[i].toString());
            }
        }


    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

-1

As pointed out by other people in the comments, the problem is caused by Java “approximation” of the values of a double.

Change it in BigDecimal.

Refer to this question for additional information.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.