2

私のプログラムの目的は、可能なすべての変更ソリューションを特定の金額に出力することです。たとえば、

望ましい出力

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

(with 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]

ご覧のとおり、文字通りすべての可能な解決策を提供してくれます。私は上位2つの答えだけを気にします。より多くの金額が要求された場合、これが大きな問題になることは明らかです。ここに私の質問があります:私のコードに基づいて、それぞれ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 に答える