该问题希望用户返回一个最小硬币列表作为找零。例如,[.01, .10, .25] , .40 。并且(所有硬币都有 10 个供应量)应该返回 [.10, .10, .10,.10] 而不是 [.25,.1,.01,.01,.01,.01,.01]
贪心法行不通。这个问题是动态规划问题。所描述的解决方案是 O(2^n)。我们如何使用自下而上的方法将其优化到 O(n^2) 或更好?
class CoinChange {
public static List<Double> findMinRefundCombination(List<Double> inputCoins, double refundToMake) {
List<Double> minCoins = new ArrayList<>();
List<Double> coinsAccumulatedSoFar = new ArrayList<>();
double refundSoFar = 0.0d;
findMinRefundCombinationHelper(inputCoins, refundToMake, minCoins,coinsAccumulatedSoFar, 0, refundSoFar);
System.out.println(minCoins.size());
return minCoins;
}
public static void findMinRefundCombinationHelper(List<Double> inputCoins, double refundToMake, List<Double> minCoins, List<Double> coinsAccumulatedSoFar, int curIndex, double refundSoFar) {
if(refundSoFar > refundToMake || curIndex == inputCoins.size()) {
return;
}
if(refundSoFar == refundToMake) {
if(minCoins.isEmpty()) {
for(Double coin: coinsAccumulatedSoFar)
minCoins.add(coin);
} else {
if(coinsAccumulatedSoFar.size() < minCoins.size()) {
minCoins.clear();
for(Double coin: coinsAccumulatedSoFar)
minCoins.add(coin);
}
}
}
coinsAccumulatedSoFar.add(inputCoins.get(curIndex));
// findMinRefundCombinationHelper(inputCoins, refundToMake, minCoins, coinsAccumulatedSoFar,curIndex,refundSoFar + inputCoins.get(curIndex));
findMinRefundCombinationHelper(inputCoins, refundToMake, minCoins, coinsAccumulatedSoFar, curIndex + 1, refundSoFar + inputCoins.get(curIndex));
coinsAccumulatedSoFar.remove(coinsAccumulatedSoFar.size() - 1);
findMinRefundCombinationHelper(inputCoins, refundToMake, minCoins, coinsAccumulatedSoFar, curIndex + 1, refundSoFar);
}
public static void main(String[] args) {
List<Double> inputCoins = new ArrayList<>();
inputCoins.add(.01);
// inputCoins.add();
inputCoins.add(.10);
inputCoins.add(.25);
inputCoins.add(0.50);
inputCoins.add(1.0);
double refundToMake = 0.40;
List<Double> minCoins = findMinRefundCombination(inputCoins, refundToMake);
for(Double coin: minCoins)
System.out.print(coin + " ");
System.out.println();
}
}
最佳答案
如果您要表示的金额足够低,则可以将此问题转换为背包的变体。
在评论中,您声明所有数字的精度都是小数点后两位,因此所有数字都可以通过乘以 100 转换为整数。让我们也从原始输入中给出的每个硬币中创建 10 个硬币,并且声明我们最多可以使用每个新硬币一次。
这里的想法类似于Knapsack:让我们引入一个函数F(k, i)
,它表示如果我们只使用一些第一个 i
硬币。例如,F(0, i)
是 0,因为对于我们可用的任何硬币子集,我们都可以不使用任何硬币来实现总和 0。 F(k > 0, 0)
是未定义的,因为我们不能在不使用硬币的情况下获得大于 0 的总和,并且 F(|第一个硬币的值(value)|, 1)
等于 1。请注意 F(k, 10N)
将是问题的答案。
这里的循环关系是 F(k, i) = min(F(k, i - 1), F(k - |硬币 i 的值(value)|, i - 1))
k, i
的适用值。在英语中,我们说“要么我们使用第 i 个硬币,在这种情况下总和必须增加它的值(value),要么我们没有”。
关于algorithm - 最小的硬币变化(有限供应)具有更好的时间复杂度讨论,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56222997/