1

そこで私は、特定の金額に到達できる特定の金種セットの「コイン」の最小数を計算する問題に対して、再帰的なアルゴリズムを作成しました。アルゴリズムは機能しているように見えますが、再帰的であり、いずれかを選択する前に可能なすべてのオプションを計算するため、使用されている金種も印刷する方法を考え出すのに苦労しています. したがって、基本的に、使用可能なコインの最小数を計算できますが、どのコインであるかは計算できません。これが、コードと、それを駆動するために使用している小さなメイン メソッドです。アルゴリズム自体を合理化するための提案も大歓迎です。

public class DynamicCoinChange {

    public static void main(String[] args) {
        int[] denoms = {1, 6, 10, 25};
        int numCoins = dynamicCoinChange(denoms, 18, 3);
        System.out.println(numCoins);
    }

    public static int dynamicCoinChange(int[] denoms, int amt, int start) {
        if (amt == 0 || start < 0) {
            return 0;
        } else if (amt == 1) {
            return 1;
        } else if (denoms[start] > amt || 
                dynamicCoinChange(denoms, amt, start-1) < 
                (1 + dynamicCoinChange(denoms, amt-denoms[start], start)) &&
                !(dynamicCoinChange(denoms, amt, start-1) == 0)) {
            return dynamicCoinChange(denoms, amt, start-1);
        } else {
            return 1 + dynamicCoinChange(denoms,amt-denoms[start], start);
        }
    }
}
4

2 に答える 2

0

最小変化問題は、再帰的にプログラムする必要はありません。より単純な反復方式でプログラムできます。

int[] denoms = { 1, 6, 10, 25 };
int amt = 18;
double[] min = new double[ amt + 1 ];

for( int i = 1; i < min.length; i++ ) { // We're keeping min[ 0 ] as 0/
    min[ i ] = Double.POSITIVE_INFINITY;
}

for( int i = 1; i <= amt; i++ ) {

   for( int j = 0; j <= N - 1; j++ ) {

       if( denoms[ j ] <= i && min[ i - denoms[ j ] ] + 1 < min[ i ] )
           min[ i ] = min[ i - denoms[ j ] ] + 1;

   }
}

ここで、ソリューションはエントリ min[amt] になります。

于 2013-03-17T03:11:39.903 に答える
0

次の 2 つの情報を知る必要があります。

  • 最適解としてコインが選ばれたとき
  • 最適解のためにどのコインが選ばれたか

あなたのアルゴリズムによれば、私たちはあなたが戻るたびにコインを選択することを知っています1. また、 で選択されたコインのインデックスが であることもわかっていstartます。したがって、この問題を解決するための情報があります。

ここではパフォーマンスは問題にならないので、コインが選択されたときに満たされるコイン パラメータを単純に渡します。

public static int dynamicCoinChange(int[] denoms, int amt, int start, ArrayList<Integer> coins) {
    if (amt == 0 || start < 0) {
        return 0;
    } else if (amt == 1) {
        coins.add(1);
        return 1;
    } else if (denoms[start] > amt 
            // Note that these calls are not guaranteed to be in our solution
            // Thus, we make a copy to prevent the calls from modifying our solution
            || dynamicCoinChange(denoms, amt, start-1, new ArrayList<Integer>(coins)) < 
                (1 + dynamicCoinChange(denoms, amt-denoms[start], start, new ArrayList<Integer>(coins))) 
            && !(dynamicCoinChange(denoms, amt, start-1, new ArrayList<Integer>(coins)) == 0)) {
        return dynamicCoinChange(denoms, amt, start-1, coins);
    } else {
        coins.add(denoms[start]);
        return 1 + dynamicCoinChange(denoms,amt-denoms[start], start, coins);
    }
}

これにはメソッドのシグネチャを変更する必要があるため、ドライバーも変更する必要があります。

public static void main(String[] args) {
    int[] denoms = {1, 6, 10, 25};
    ArrayList<Integer> coins = new ArrayList<Integer>();
    int numCoins = dynamicCoinChange(denoms, 7, 3, coins);
    for (Integer coin : coins)
        System.out.println(coin);
    System.out.println(numCoins);
}

再帰呼び出しの最後に、coins時系列で選択されたコインのリストが含まれている必要があります。

于 2013-03-17T03:12:19.130 に答える