CODEWITHSUNDEEP
algorithmrecursionoptimizationdata-structuresdynamic-programming
Loqa
Loqa

Reputation: 79

Minimal coin change(limited supply) with better time complexity discussion

The problem wants user to return a list of minimal coins as a change. For example , [.01, .10, .25] , .40 . And (all coins have 10 number of suppplies) should return [.10, .10, .10,.10] but not [.25,.1,.01,.01,.01,.01,.01]

The greedy approach doesn't work. This problem is Dynamic Programming problem. The described solution is O(2^n). How can we optimize it to O(n^2) or better with bottom up approach?


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

Upvotes: 0

Views: 206

Answers (1)

eldar
eldar

Reputation: 413

If the amount you are trying to represent is low enough, this problem can be converted to a variation of Knapsack.

In the comments you state that the precision of all numbers is two decimal places, so all the numbers can be converted to integers by multiplying them by 100. Let's also create 10 coins out of each coin given in the original input, and declare that we can use each of the new coins at most once.

The idea here is similar to Knapsack: let's introduce a function F(k, i) that represents how many coins we need to achieve sum k if we only use some of the first i coins. For example, F(0, i) is 0 because with any subset of coins available to us, we can achieve sum 0 using none of them. F(k > 0, 0) is undefined because we can't achieve a sum above 0 using no coins, and F(|value of the first coin|, 1) is equal to 1. Note that F(k, 10N) will be the answer to the problem.

The recurrent relation here is F(k, i) = min(F(k, i - 1), F(k - |value of coin i|, i - 1)) for applicable values of k, i. In English, we are saying "either we use the i-th coin, in which case the sum must have increased by its value, or we didn't".

Upvotes: 1

Related Questions