0

ここにコードがあります。これは、特定の金額を変更するためのコインの最小構成を返すことを目的としています。sum と金種のリストの 2 つのパラメータを取ります。コンパイルエラーはなく、プログラムは出力を提供するように機能しますが、得られるものはまったく正しくありません。これに関するヘルプは大歓迎です。

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

一般的に、あなたのコードは非常に複雑です! 私はいくつかの変更を試みましたが、あなたが何をしようとしているのかを正しく理解していれば、適切な値を得るには数行を追加するだけで十分です。もちろん、すべての可能な組み合わせでこれを試したわけではないので、結果を壊すものを提示してください!

ミンコイン方式:

  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 に答える