0

我在这里有我的代码，它旨在返回硬币的最小配置，以便为给定的金额进行更改。它有两个参数，总和和面额列表。我没有编译错误，程序可以提供输出，但我得到的并不完全正确。对此非常感谢任何帮助。

//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);

 } 

}

请随时评论风格和算法的潜在改进领域。谢谢！

4

1 回答 1

1

一般来说，您的代码非常复杂！我尝试了一些更改，如果我正确理解您要做什么，只需几行新行就足以获得正确的值。当然，我还没有尝试过所有可能的组合，所以欢迎您向我展示一个破坏结果的组合！

Mincoins方法：

  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 方法 @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);
    }
于 2013-08-01T22:44:15.850 回答