2

我的程序的目标是输出给定金额的所有可能的变更解决方案，例如

期望的输出

Change: 9
[1, 1, 1, 1, 5]
[1, 1, 1, 1, 1, 1, 1, 1, 1]

（9 = $0.09）但是我的输出有点不同，我的输出看起来像这样

我的输出

Change: 9
[1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 5]
[1, 1, 1, 5, 1]
[1, 1, 5, 1, 1]
[1, 5, 1, 1, 1]
[5, 1, 1, 1, 1]

如您所见，它从字面上为我提供了所有可能的解决方案。我只关心前两个答案。很明显，当要求更大的数量时，这将是一个大问题。所以这是我的问题：根据我的代码，如何将其修复到每个仅显示一个组合的位置？

代码

import java.io.*;
import java.util.*;
import java.lang.*;

public class homework5 {

 public static int change;

   public static void main(String[] args)
     throws FileNotFoundException { //begin main

     ArrayList<Integer> coinTypes = new ArrayList<Integer>();//array to store
                                                             //coin types
     ArrayList<Integer> answerCoins = new ArrayList<Integer>(); //to contain solutions

     Integer i;
     File f = new File (args[0]);
     Scanner input = new Scanner(f); //initialize scanner
       input.nextLine();
       while(input.hasNextInt()) {
           i = input.nextInt();
           coinTypes.add(i); //add all ints to file
       }
        change = coinTypes.get(coinTypes.size()-1);
        coinTypes.remove(coinTypes.size()-1);
            System.out.println("Change: " + change);

    findChange(change, coinTypes, answerCoins);

   }
    private static void findChange(int change, List<Integer> coinTypes,
                            List<Integer> answerCoins) { //contains means of
                                             //finding the change solutions
        if(change == 0) {
           //base case
          System.out.println(answerCoins);
        }
          else if(change < 0) {
           //if negative it can't be a solution
        } else {
          for(int coin = 0; coin < coinTypes.size(); coin++) {

                 answerCoins.add(coinTypes.get(coin)); //choose
                 findChange(change-coinTypes.get(coin), coinTypes, answerCoins);//explore
                 answerCoins.remove(answerCoins.size()-1);    //un-choose
          }

        }

    }

}

感谢您的任何和所有答案，请尽量忽略任何其他错误，我想先解决这个问题。谢谢！！

4

2 回答 2

5

一个简单的方法是避免创建解决方案，其中添加到数组末尾的硬币的值小于数组的当前末尾（当然，当数组为空时，总是在第一次迭代时添加）。这自然会删除所有这些重复项。它很容易实现，因为它不涉及大量额外的逻辑，只是确保您不会在搜索中将较小的硬币添加到数组的末尾。

它也非常有效：您的递归甚至不会下降到那些分支，并且您不必进行任何类型的搜索来寻找重复的解决方案。

作为一个额外的副作用，您生成的所有解决方案都将包含从最小到最大排序的硬币。（相反，如果您避免在数组末尾添加价值较大的硬币，您的解决方案将包含从最大到最小排序的硬币。无论哪种方式，这是一个偏好问题。）

于 2014-11-26T04:11:21.313 回答
2

您可以将 findChange() 修改为

private static void findChange(int change, List<Integer> coinTypes,
                        List<Integer> answerCoins, int lastcoin);

lastcoin 是指您添加的最后一个硬币。在循环中，您不需要迭代 coinTypes 中的所有硬币。相反，您只对小于或等于 lastcoin 的硬币进行降序迭代

  for(coin in coins if coin <= lastcoin) { // must in descending order
         answerCoins.add(coinTypes.get(coin)); //choose
         findChange(change-coinTypes.get(coin), coinTypes, answerCoins, coin);//explore
         answerCoins.remove(answerCoins.size()-1);    //un-choose
  }

那么，你只会得到 [5, 1, 1, 1, 1]，而 [1, 5, 1, 1, 1] 永远不会发生

于 2014-11-26T04:14:27.713 回答