1

動的計画法に関するコードのこの部分が与えられました（これは、コインの変更の最適な組み合わせを見つけます。たとえば、値3と4-> {3,4}の2つのコインがある場合、および作成したい量です。変更は、たとえばsum = 11です。答えは、合計3枚のコインが必要であるということです（値= 4のコイン2枚、値= 3のコイン1枚）。以下のコードは正常に機能していますが、希望どおりではありません

。次のようなより明確な答えが得られるように、以下のコードをリバースエンジニアリングしようとしています。

Total coins:3 , #of Coins with value "3" = 1, #of Coins with value "4" = 2

指定された金額の合計コイン数は、この配列minimum[sum]から見つけることができます。しかし、私が取得しようとしている残りの情報（どのコインがどの値であるか）は、ほとんど見つけることができないようです。また、配列coins [sum] [0]からは、最後に使用されたコイン、この例では3のみを見つけることができます。

Inputs: sum=11 ,int[] valueCoins = new int[]{3,4}; 
Output:
1 10011 0(0)
2 10011 0(0)
3 1 3(0)
4 1 4(0)
5 10011 0(0)
6 2 3(3)
7 2 3(4)
8 2 4(4)
9 3 3(6)
10 3 3(7)
11 3 3(8)

ご覧のとおり、1から11までのすべてをチェックしますが、11に達すると、正しい量のコイン（3）と最後に使用されたコイン（3）が保存されます。

public class MinimumCoin {

    public static void main(String args[]){

        int[] valueCoins = new int[]{3,4};
        int sum = 11;
        int[] minimum = new int[sum+1];
        int[][] coins = new int[sum+1][2];

        /* initializing the minimum of every sum to infinity */
        for(int i = 1; i < minimum.length; i++){
            minimum[i] = sum + 10000;
        }
        /* initializing that for minumum sum of zero, 0 coin is required */
        minimum[0] = 0;

        for(int i = 1; i <= sum; i++){
            for(int j = 0; j <valueCoins.length; j++){
                if(valueCoins[j] == i){
                    minimum[i] = 1;
                    coins[i][0] = i;
                    coins[i][1] = 0;
                }
                else if((valueCoins[j] < i) && (((minimum[i-valueCoins[j]]) + 1) < minimum[i])){

                    minimum[i] = (minimum[i-valueCoins[j]]) + 1;
                    coins[i][0] = valueCoins[j];
                    coins[i][1] = (i-valueCoins[j]);
                }
            }
        }

        for(int k = 1; k < minimum.length; k++){
            System.out.println( k + " " + minimum[k] + " " + coins[k][0] +"("+ coins[k][1] +")");
        }
    }
}

ご入力いただきありがとうございます。

〜よろしく、S

4

1 に答える 1

1

問題は、の値がカウントではなくコインcoinsの値であるということです。coins：

0 0 0 3 0 0 3 3 4 3 3 3 
0 0 0 0 4 0 3 4 4 6 7 8

したがって、カウントを再構築する必要があります。

for(int k = 1; k < minimum.length; k++)
{
   int count1 = 0, count2 = 0, pos = k;
   if (coins[pos][1] > 0)
      while (true)
      {
         if (coins[pos][0] == 3) count1++;
         if (coins[pos][0] == 4) count2++;
         if (coins[pos][1] == 3) count1++;
         if (coins[pos][1] == 4) count2++;
         if (coins[pos][1] < 5) // stop when 0/3/4
            break;
         pos = coins[pos][1];
      }
   System.out.println(k + " " + minimum[k] + " " +
                      count1 + " of coin 3, " + count2 + " of coin 4");
}

これらは、問題を解決するためのオプションでもあります。

  • コインの出現回数ごとに行を作成します。コインが2つあり、それぞれが5回出現する場合、5x2=10行になります。

  • 次のような行があります。

    • 行1=1コイン1の1
    • 行2=1コイン2の1
    • 行3=2コイン1の2
    • 行4=2コイン2の2
    • 行5=コイン1の4
    • 行6=コイン2の4
    • 行7=コイン1の8
    • 行8=コイン2の8
    • ..。

後者は見た目はより複雑ですが、より多くのコインに対してはるかに少ない行があるため、推奨されます。

于 2013-02-23T11:13:08.460 に答える