硬币改变制造商的解决方案太多了

Question

例如,我的计划的目标是将所有可能的变更解决方案输出到给定数额的金额

期望的输出

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
          }

        }

    }

}

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

Answer 1

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

它也非常有效:您的递归甚至不会进入那些分支,您不必进行任何类型的搜索重复解决方案.

作为奖励副作用,您所得到的所有解决方案都将包含从最小到最大的硬币.(相反,如果您避免在阵列的末尾添加更大的有价值的硬币,您的解决方案将包含从最大到最小的硬币.无论哪种方式,这都是优先考虑的问题.)