如何解决金额为双精度而不是整数的硬币兑换问题

Question

我如何着手解决一个类似的问题，在这个问题中，金额可以是一个双倍值（例如19.12），而不是严格意义上的int（例如19），并且测试用例将包括美元钞票和硬币？

在典型的leetcode问题中，我将创建一个dp数组，该数组将存储最少的硬币，以构成当前使用的数量。使用自底向上的处理，我将从最小的子问题（dp[0]=0）开始，然后解决手头的问题，如下所示：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for(int i = 0; i <= amount; i++) {
            for(int j = 0; j < coins.length; j++) {
                if(coins[j] <= i) {
                    dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]);
                }
            }
        }
        return dp[amount] > amount ? - 1 : dp[amount];
    }
}

编辑

乔尼的回答成功了。这是我的最终解决方案。基本上，最初的解决方案只能读取int金额（整美元金额0美分），但是现在，下面的程序将双金额分离为钞票和硬币，并将两者转换为int值。然后，不管最初的解决方案是做什么的，新的解决方案只是分别对钞票和硬币做同样的事情。不确定这是否有意义，但解决办法是：

import java.util.Arrays;
import java.util.Scanner;

class Main {
    public static void main (String[] args) {
        int[] billDeno = new int[] {500,200,100,50,20,10,5,2,1};
        int[] coinDeno = new int[] {50,25,10,5,2,1};
        Scanner input = new Scanner(System.in);
        System.out.printf("Enter amount: ");
        double amount = input.nextDouble();
        int y = coinChange(billDeno, coinDeno, amount);
        System.out.println(y);
    }
    
    public static int coinChange(int[] billDeno, int[] coinDeno, double amount) {        
        int numDollars = (int) amount;
        int numCents = (int) ((amount - numDollars) * 100 + 0.5f);
        
        int[] dpDollars = new int[numDollars + 1];
        int[] dpCents = new int[numCents + 1];
        
        Arrays.fill(dpDollars, numDollars + 1);
        Arrays.fill(dpCents, numCents + 1);
        
        dpDollars[0] = 0;
        dpCents[0] = 0;
        
        for(int i = 0; i <= numDollars; i++) {
            for(int j = 0; j < billDeno.length; j++) {
                if(billDeno[j] <= i) {
                    dpDollars[i] = Math.min(dpDollars[i], 1 + dpDollars[i - billDeno[j]]);
                }
            }
        }
        for(int i = 0; i <= numCents; i++) {
            for(int k = 0; k < coinDeno.length; k++) {
                if(coinDeno[k] <= i) {
                    dpCents[i] = Math.min(dpCents[i], 1 + dpCents[i - coinDeno[k]]);
                }
            }
        }
        return dpDollars[numDollars] + dpCents[numCents] > amount ? -1 : dpDollars[numDollars] + dpCents[numCents];
    }
}

这可能看起来像一个hacky解决方案（尤其是接近尾声），所以请随时发布更优化的解决方案。感谢所有的帮助！




Answer 1

现在这里有一个很好的答案。

我想如果你把int改成double，它可能会工作，也可能不会。但是，它不会通过LeetCode，因为这不是所需的输入/输出：

class Solution {
    public double coinChange(double[] coins, double target) {
        if (target < 1)
            return 0;
        return helper(coins, target, new double[target]);
    }

    private double helper(double[] coins, double rem, int[] count) {
        if (rem < 0)
            return -1;
        if (rem == 0)
            return 0;
        if (count[rem - 1] != 0)
            return count[rem - 1];
        int min = Integer.MAX_VALUE;
        for (double coin : coins) {
            double res = helper(coins, rem - coin, count);
            if (res >= 0 && res < min)
                min = 1 + res;
        }

        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];

    }
}

您的输入/输出可能如下所示：

coins = [1.0, 2.0, 5.0, 0.01, 0.1, 0.25, 0.5], amount = 19.12

您可能需要调试它，可能有一些typebug。

对于int，这将通过LeetCode：

class Solution {
    public int coinChange(int[] coins, int target) {
        if (target < 1)
            return 0;
        return helper(coins, target, new int[target]);
    }

    private int helper(int[] coins, int rem, int[] count) {
        if (rem < 0)
            return -1;
        if (rem == 0)
            return 0;
        if (count[rem - 1] != 0)
            return count[rem - 1];
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = helper(coins, rem - coin, count);
            if (res >= 0 && res < min)
                min = 1 + res;
        }

        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];

    }
}

• 有关更多详细信息，请参见讨论板。这里有许多公认的解决方案，包括各种语言和解释、高效算法以及渐近时间/空间复杂性分析^1,2

Answer 2

这不适用于double。

许多十进制分数（如0.10）不能精确表示为二进制浮点数。当您在Java程序中编写0.10或0.30时，您可以得到最佳近似值，但不能得到精确值。看，浮点数学被打破了吗？

例如，0.30不是0.10的三倍。这个程序不会找到一种方法来改变0.3。

如果你将金额和硬币价值乘以100，以美分为单位，并使用int或long。同样有效的方法是使用BigDecimal类而不是double，但是您必须使用方法调用而不是算术运算符。