ナップザックダイナミックプログラミング

Question

これは動的プログラミングを必要とする一般的なナップザック問題であり、アイテムの供給には制約がありません。私はこのクラスでクラスに取り組んできました。アルゴリズムを使って数時間プレイしてみましたが、私はまだそこに着いていません。

public static int fitBackPack(int[] W, int[] V, int T){ 
    int[] Opt = new int[T+1]; 
    Opt[0]=0; 
    for (int i=1; i<=T; i++){ 
     int localMax=0; 
     int globalMax=0; 
     for (int j=0; j<W.length; j++){ 
      if (W[j]<=i){ 
       localMax = (T%W[j]<=W[j]) ? V[j] : V[j]+Opt[T-W[j]]; 
       globalMax = (localMax>=globalMax) ? localMax : globalMax; 
      } 
     } 
     Opt[i]=globalMax; 
    } 
    //debugging purposes 
    for (int k=0; k<Opt.length; k++){ 
     System.out.println("Opt["+k+"] = "+Opt[k]); 
    } 
    return Opt[T]; 
} 

この方法は、重量とそれぞれの項目の値、および最大量を表す整数のTを含む、W及びVのソートされた配列を取ることになっています。私の出力では、T = 21までのすべてが動作しますが、その後は貪欲なアルゴリズムのように動作しているように見えますが、これはまったく私が望んでいないものです。どんなヒントもありがとう、ありがとう！

Answer 1

ヒント：テストケースを使用して条件による （X％yを< = Y）==真

すべての今して真理値表は、あなたがこれらを見つけましょう。 一般的な使用法やエッジの場合には、いくつかの自動テストを設定する方が良いでしょう。

Answer 2

あなたのアルゴリズムは欲張りなもののように動作しているので、おそらくlocalMaxの計算に問題があります（貪欲アルゴリズムは最も高いローカル値を探します）。あなたのコードを見ることによって、あなたは間違った方法でlocalMaxを得ているようです。ヒント、Math.max()機能を参照してください。