algorithm - 最小的硬币变化(有限供应)具有更好的时间复杂度讨论

Question

该问题希望用户返回一个最小硬币列表作为找零。例如，[.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();
  }
}

Answer 1

如果您要表示的金额足够低，则可以将此问题转换为背包的变体。

在评论中，您声明所有数字的精度都是小数点后两位，因此所有数字都可以通过乘以 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)，要么我们没有”。