java - 贪心算法给出可疑结果

Question

我正在实现一个简单的贪心算法:

目标:在以下硬币类型中，使用尽可能少的硬币来偿还用户的零钱； 25 美分 (0.25)、10 美分 (0.10)、镍 (0.05) 和便士 (0.01)。

输入:用户应找零的金额。

输出:用于回馈用户的硬币总数。

下面是我的代码片段:

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

---

结果:

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

---

我决定使用 while 循环和模运算符来做到这一点。如果 changeOwed 等于 0，则无需执行 while 循环，因为所有更改都已得到返回。此外，如果 changeOwed % COINTYPE(“COINTYPE”是任意占位符)等于 changeOwed，则表明 COINTYPE 大于 changeOwed(剩余零钱)。在这种情况下，程序会继续执行下一个带有较小 COINTYPE 的 while 循环。

如上所示，该算法似乎在使用的硬币数量方面产生了正确的输出。但是，与上一个示例一样，剩余的零钱数量似乎相去甚远。我知道由于位数有限，计算机无法进行完美的算术运算。但是，为什么剩余的变化量从 0.32 急剧增加到 3+？

Answer 1

它不是 3。它是 3E-18，这是一个非常小的数字(0. 18-零 3)。

这可能是由于使用doubles 造成的。 It's a floating point error.

如果你想避免这种使用 BigDecimal