3

nに与えられる可能性のあるすべての変更セットを列挙するために、Javaコインの変更問題を試しています。

私の論理は次のようになります。

while n >= denom m {
array[]+= denom m
n-= denom m
}
list.add[array[]]

return coinChanger(++denom)

私のコード:

public List<Integer> makeChange(int change) {

    int[] denominations;
    denominations = new int[]{1, 5, 10, 25};

    return changeMaker(change, denominations, 0);
}

public List<Integer> changeMaker(int change, int[] denominations, int index) {
    List<Integer> resultsList = new ArrayList<Integer>();
    int[] resultDenom;
    resultDenom = new int[4];

    if (change <= 1) {
        return resultsList;
    }

    while (change >= denominations[index]) {
        resultDenom[index] += denominations[index];
        System.out.println("ResultsDenom: " + resultDenom[index]);
        change -= denominations[index];
    }
    resultsList.add(resultDenom[index]);

    for (int val : resultDenom) {
        System.out.println(val);
    }


    if (change > denominations[index]) {    
        return changeMaker(change-=denominations[index], denominations, ++index);       

    }
    return resultsList;
}

これは、すべての列挙の 1 セットだけを出力します。

出力：

27
0
0
0
RESULT CHANGE PERMUTATIONS LIST: [27]

質問:

それらの1つが終了したら、次の金種に移動する方法を理解するのに苦労しています...金種配列の次のインデックスに移動することになっていることは知っています...しかし、それは次のコインを追加するだけです.. . 次の最大のコインを追加してから、再帰的に次のコインにドロップするようにするにはどうすればよいですか?

ありがとう！

*編集**

public List<Integer> makeChange(int change) {

    int[] denominations;
    denominations = new int[]{25, 10, 5, 1};

    return changeMaker(change, denominations, 0);
}

public List<Integer> changeMaker(int change, int[] denominations, int index) {
    List<Integer> resultsList = new ArrayList<Integer>();
    int[] resultDenom;
    resultDenom = new int[4];

    if (change <= 1) {
        return resultsList;
    }

    if (index > 3) { 
        return resultsList;
    }
    //if 27 >= 25
    if (change >= denominations[index]) {   

        //[+25, 0, 0, 0]
        resultDenom[index] += denominations[index];

        //{  LIST  } <--- [25, 0, 0, 0]
                //List now contains { [25, 0, 0, 0], }, still need all other permutations
        resultsList.add(resultDenom[index]);

        //27 - 25, 
        return changeMaker(change-=denominations[index], denominations, ++index);       

    }
    return resultsList;
}

望ましい出力: リストのリスト... 27 セント:

LIST{ [1, 0, 0, 2], [0, 2, 1, 2], [0, 1, 3, 2]... etc}

4

2 に答える 2

6

最も簡単な解決策は、各ステップで 2 つのバリアントに再帰することです (まだ完了していない場合)。

  1. 現在のコインで続行: リストに追加して再帰します。
  2. 次のコインに切り替える: コインの位置を増やして再帰します。

次のようになります。

public class Coins {
  static final int[] DENOMINATIONS = {25, 10, 5, 1};

  public static void change(int amount) {
    change(amount, new ArrayList<Integer>(), 0);
  }

  private static void change(int remaining, List<Integer> coins, int pos) {
    if (remaining == 0) {
      System.out.println(coins);
    } else {
      if (remaining >= DENOMINATIONS[pos]) {
        coins.add(DENOMINATIONS[pos]);
        change(remaining - DENOMINATIONS[pos], coins, pos);
        coins.remove(coins.size() - 1);
      }
      if (pos + 1 < DENOMINATIONS.length) {
        change(remaining, coins, pos + 1);
      }
    }
  }
}

リストを収集したい場合は、コインが追加されたリストのコピーを作成する必要があります (呼び出しから戻った後にコインを削除するのではなく)。

于 2013-05-10T23:18:10.850 に答える
-1

あなたのコードは、解決しようとしている問題に対して少し複雑に見えます

この擬似コードを実装してみてください

  getChange(int totalCents)
  {
      if (totalCents > 25)
      {
         print "25";
         getChange(totalCents - 25);
      } 
      else (totalCents > 10)
      {
         // same for 10
      }
      else (totalCents > 5)
      {
         // same for 5
      }
      else
      {
         // print out number left as pennies
      }
  }

if ステートメントを、配列インデックスと for ループを使用してハードコードされた値に簡単に置き換え、値を記録したい方法で印刷することができます。それが役立つことを願っています。

于 2013-05-10T19:44:29.947 に答える