与えられた量の変更を行う組み合わせを決定する

Question

私の割り当ては、無差別にアルゴリズムを書いて、別々の方法の数、所与の量の変化の関連する組み合わせを決定することです。ペニー（1セント）、ニッケル（5セント）、10セント（10セント）、および25セント（25セント）のコインを使用して変更が行われます。

入力：6つの異なる方法で製造することができ、それらは次のとおり：16

出力（それは16セントの変化を意味する）

1. 16ペニー。
2. 11ペニー、1つのニッケル
3. 6ペニー、1つのダイム
4. 6ペニー、2枚の硬貨
5. 1ペニー、3枚の硬貨
6. 1ペニー、1つのニッケル、1つのダイム

マイアルゴリズムは、指定された変更量に対して可能なすべての変更の組み合わせを生成する必要があります。

---

私はこのようなアルゴリズムの開始方法を完全に失っています。私を得るためのあらゆるインプットや洞察力はすばらしいものになるでしょう。

Answer 1

ブルートフォースアルゴリズムのアイデアを説明しましょう。私はここで再帰を使用します。

cセントの変更が必要ですか？その後

c = p * PENNY + n * NICKEL + d * DIME + q * QUARTER 

または単にcを検討し、

c = (p * 1) + (n * 5) + (d * 10) + (q * 25) 

は今、あなたはcの値に等しいp、n、dとq可能なすべての値を通過する必要があります。再帰を使用して、それぞれp in [0, maximumPennies]を経由してそれぞれn in [0, maximumNickels]を通過します。それぞれについてnd in [0, maximumDimes]を通過してください。各dの場合、それぞれq in [0, maximumQuarters]を通過します。

p in [0, maximumPennies] AND c >= p 
    | 
    +- n in [0, maximumNickels] AND c >= p + 5n 
     | 
     +- d in [0, maximumDimes] AND c >= p + 5n + 10d 
      | 
      +- q in [0, maximumQuarters] AND c >= p + 5n + 10d + 25q 

これらの手順で同等であれば解決策があります。

Answer 2

これに再帰を使用してください。 あなたの関数は2つのパラメータを取る必要があります - あなたが使用できる最大値と支払うべき金額（あなたが最初に繰り返しを避ける必要があります）。 このような方法で関数を作成します。単純なケース（1,5,10など、それぞれペニーを取ることが許可されている場合はニッケル、それぞれニッケル）は簡単な解決策です。また、それぞれの場合について、許可された全てのタイプのコインを1つ取る（例えば、許可された最大値より大きくない）ようにして、再帰的に続行する。

これが役に立ちます。

Answer 3

この問題については、それを解決するためのサブ問題に分割し、問題を変更して解決策を調整することで考えることができます。

あなたのケースでは、まずペニーだけを使って問題を解決しようとすることができます（もちろん明らかな解決策は1つしかありません）。そして、ニッケルとペニーを見てそこのすべての組み合わせを見ます。これを改善するために、アルゴリズムの初期段階のソリューションを再利用できます。

Answer 4

まあ、強引な解決策を望むなら、あなたは非常に素朴なrecursive approachで始めることができます。しかし効率的になるにはdynamic programming approachが必要です。再帰的なアプローチのために

：

1. find out the number of ways you can make using penny only. 
2. do the same using penny and nickel only. (this includes step 1 also) 
3. the same using penny, nickel and dime only (including step 2). 
4. using all the coins (with all previous steps). 

ステップ1は、それを行うための唯一の方法は簡単です。

ステップ2については、再帰は次のようにすべきである：

number of ways to make n cent using penny and nickel = 
    number of ways to make (n - [1 nickel]) using penny and nickel 
    + number of ways to make n cent using penny only 

ステップ3：

number of ways to make n cent using penny, nickel and dime = 
    number of ways to make (n - [1 dime]) using penny, nickel and dime 
    + number of ways to make n cent using penny and nickel only 

ステップ4と同様です。

覚えておくべきこと：に0セントを1つの（つまりゼロコインを使用）とすることができます。これは基本ケースです。

Answer 5

public class PrintAllCoinCombinations { 


    static int findChange(int arr[], int index , int value, String str){ 

     if(value == 0){ 
      System.out.println(str); 
      return 1; 
     } 
     if(index<0){ 
      return 0; 
     } 
     if(value<0){ 
      return 0; 
     } 

     int excl = findChange(arr,index-1,value,str); 

     str += " "+ arr[index]; 

     int incl = findChange(arr,index,value-arr[index],str); 

     return incl + excl; 

    } 

    public static void main(String [] arg){ 
     int arr[] = {1,5,10,25}; 
     String s = ""; 
     int result = findChange(arr,3,16,s); 
     System.out.println(result); 
    } 
}