Минимальная замена монет (ограниченная поставка) с лучшим обсуждением сложности во времени - PullRequest
Новая
       22

Минимальная замена монет (ограниченная поставка) с лучшим обсуждением сложности во времени

0 голосов
/ 20 мая 2019

Проблема требует, чтобы пользователь возвращал список минимальных монет в качестве изменения.Например, [.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();
  }
}

1 Ответ

1 голос
/ 20 мая 2019

Если сумма, которую вы пытаетесь представить, достаточно мала, эту проблему можно преобразовать в разновидность рюкзака.

В комментариях вы утверждаете, что точность всех чисел составляет два десятичных знака, поэтому все числа можно преобразовать в целые числа, умножив их на 100. Давайте также создадим 10 монет из каждой монеты, заданной в исходном вводе, и объявите, что мы можем использовать каждую из новых монет не более одного раза.

Идея здесь похожа на рюкзак: давайте введем функцию F(k, i), которая представляет, сколько монет нам нужно, чтобы получить сумму k, если мы используем только некоторые из первых i монет. Например, F(0, i) равно 0, потому что с любым подмножеством монет, доступных нам, мы можем получить сумму 0, не используя ни одну из них. F(k > 0, 0) не определено, потому что мы не можем получить сумму выше 0 без монет, а F(|value of the first coin|, 1) равно 1. Обратите внимание, что F(k, 10N) будет ответом на проблему.

Здесь рекуррентное соотношение F(k, i) = min(F(k, i - 1), F(k - |value of coin i|, i - 1)) для применимых значений k, i. На английском мы говорим: «либо мы используем i-ую монету, в этом случае сумма должна была увеличиться на ее стоимость, либо мы ее не увеличили».

...