CODEWITHSUNDEEP
javarecursiondynamic-programmingbacktracking
brain storm
brain storm

Reputation: 31272

need help in fixing this code on dynamic programming/ recursion on calculating the minimum coins using Java

I have my code here, which is aimed to return the minimum configuration of coins to make change for a given sum. It takes two parameters, sum and a list of denominations. I have no compilation error and the the program works to give output, but not quite right in what I get. Any help on this much appreciated.

//this program calculates the minimum coins and distribution of
//denominations required to make change for a given sum
import java.util.*;
import java.io.*;
public class MinCoinCollectionBacktrack {
   private int sum;
   private List<Integer> coins;

   //constructor that takes sum and list of denominations
   //such as [1,5,10,25]
   public MinCoinCollectionBacktrack(int amount,List<Integer> denominationList) {
      sum=amount;
      coins=denominationList;
  }

  //calculate the minimum coins
  //uses map to store sum-->list of combinations
  //eg 3-->[2,1], 4 -->[2,2] for a given denomination list of [1,2,5]
  public  List<Integer> Mincoins() {
   Map<Integer, List<Integer>> lenChoices=new HashMap<Integer,List<Integer>>();
      int maxdenomination=Collections.max(coins);
      Integer sum1= new Integer(sum);
   return minCoins(lenChoices,sum,maxdenomination);

  }

  //wrapper method for MinCoins, it takes a map and updates as when
  //minimum configuration of a sum is found. stores the value
  //as described above
  private List<Integer> minCoins(Map<Integer, List<Integer>> lenChoices, int value,int maxdenomination) {
  //check if sum is a key in map, then return its value
   if (lenChoices.containsKey(value)) {
      return lenChoices.get(value);
  //check if the coinlist contains sum, if yes, it creates a
  //new key value pair to the Map
   } else if (coins.contains(value)) {
      List<Integer> newlist = new ArrayList<Integer>();
      newlist.add(value);
      lenChoices.put(value,newlist);
      return lenChoices.get(value); 
  //if the denomiation is > sum, just return empty list        
   } else if (maxdenomination > value) {
      List<Integer> newlist = new ArrayList<Integer>();
      lenChoices.put(value,newlist);
      return lenChoices.get(value);
  //here is where recursive backtracking happens    
   } else {
      int minLength=0;
      List<Integer> minConfig=new ArrayList<Integer>();
      for (int coin : coins) {
         List<Integer> results = minCoins(lenChoices,value - coin,maxdenomination);
         if (!results.isEmpty()) {
            if (minLength==0 || (1+results.size()) < minConfig.size()) {               
               results.add(coin);
               minConfig=results;
               minLength=minConfig.size();
            }
         }
     }    
     lenChoices.put(value,minConfig);  
     return lenChoices.get(value);
  }
}

public static void main(String[] args) {
   System.out.println("enter the denoninations, hit enter to Zero(0) to finish");
   Scanner console = new Scanner(System.in);
   List<Integer> coinlist= new ArrayList<Integer>();
   int input = console.nextInt();
   while (input>0) {
      coinlist.add(input);
      input = console.nextInt();
   }
   System.out.println("coin collections are :"+ coinlist);
   System.out.println("enter the sum for which you need minimum coins");
   input = console.nextInt();
   MinCoinCollectionBacktrack result=new MinCoinCollectionBacktrack(input,coinlist);
   List<Integer> output = result.Mincoins();
   System.out.println("you require " + output.size() + " coins in the"
                                    + " following combination " + output);

 } 

}

please feel free to comment on potential areas of improvement on style and algorithm. Thanks!

Upvotes: 0

Views: 375

Answers (1)

Petros Koutsolampros
Petros Koutsolampros

Reputation: 2800

In general your code is quite convoluted! I tried a few changes and if I understand correctly what you are trying to do, just a few new lines are enough to get proper values. Of course I haven't tried this with every possible combination, so you are welcome to present me with one that breaks the result!

Mincoins method:

  public  List<Integer> Mincoins() {
    Map<Integer, List<Integer>> lenChoices=new HashMap<Integer, List<Integer>>();
    Collections.sort(coins, Collections.reverseOrder()); // since later on in the code you are iterating over your coins, it makes sense to sort them with the largest first so that you are slowly left with the bits that can not be divided by the larger values and have more probability to be caught be the small ones
    int maxdenomination=Collections.max(coins);
    Integer sum1= new Integer(sum);
    List<Integer> result = new ArrayList<Integer>();
    for (Integer c: coins) { //as per  Nishant Shreshth's comment, you need to check all invalid coins first and don't bother unless one which produces results is found
      println(c);
      result = minCoins(lenChoices, sum, c, 0);
      lenChoices.clear();
      if (result.size() > 0) break;
    }
    return result;
  }

minCoins method @ else {

else {
      int minLength=0;
      List<Integer> minConfig=new ArrayList<Integer>();
      for (int coin : coins) {
        List<Integer> results = minCoins(lenChoices, value - coin, maxdenomination);
        if (!results.isEmpty()) {
          if (minLength==0 || (1+results.size()) < minConfig.size()) {               
            results.add(coin);
            minConfig=results;
            minLength=minConfig.size();
          }
          break; // If we already have a result we don't need to look for the rest of the coins!
        }
      }    
      lenChoices.put(value, minConfig);  
      return lenChoices.get(value);
    }

Upvotes: 1

Related Questions