3

これは、動的計画法を必要とする典型的なナップザックの問題であり、項目の供給に制約はありません。私は自分のクラスでこれに取り組んでおり、アルゴリズムを何時間もいじってみましたが、まだそこに到達していません.

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];
}

このメソッドは、アイテムの重量と値をそれぞれ含む W と V の並べ替えられた配列と、最大重量を表す整数 T を取ることになっています。私の出力では、T = 21 まではすべて機能しますが、その後は貪欲なアルゴリズムのように機能しているように見えますが、これは私が望んでいたものとはまったく異なります。ヒントをいただければ幸いです。

4

2 に答える 2

0

あなたのアルゴリズムは貪欲なもののように振る舞うので、あなたの問題はおそらくの計算にありますlocalMax（貪欲なアルゴリズムは最高のローカル値を探すからです）。コードを見るとlocalMax、間違った方向に進んでいるように見えます。ヒント、Math.max()関数を参照してください。

于 2012-04-19T01:40:11.520 に答える
0

ヒント: (x % y <= y) == true

ときどき、テスト ケースを使用した条件の真理値表が、これらを見つけるのに役立ちます。一般的な使用法と特殊なケースのために、いくつかの自動化されたテストを設定することをお勧めします。

于 2012-04-19T01:21:31.683 に答える