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¢
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());
}
}
}
}