2

ナップザック問題の解決策 ( http://en.wikipedia.org/wiki/Knapsack_problem ) を読んだとき、なぜ引数に反復回数 n があるのか​​理解できませんでした。通過した制限を確認することで、葉のユースケースに到達できるようです。元。15KG バックパックの問題、解決策は次のようになります。

Value(n, W){ // W = limit, n = # items still to choose from
    if (n == 0) return 0;
    if (arr[n][W] != unknown) return arr[n][W]; // <- add memoize
    if (s[n] > W) result = Value(n-1,W);
    else result = max{v[n] + Value(n-1, W-w[n]), Value(n-1, W)};
    arr[n][W] = result;                // <- add memoize
    return result;
}

私の非メモ化方法は次のようになります。これは、少なくとも私にとっては理解しやすく、メモ化によって改善される可能性もあります。

static int n =5;
static int [] w = new int[]{12,2,1,4,1}; //weight
static int [] v = new int[]{4,2,1,10,2}; //value
public static int knapSack(int wt){
    int maxValue = 0,vtemp = 0, wtemp =0;
    if (wt ==0) return 0;
    for (int i=0; i<n; i++){
        if (w[i] > wt) continue;
        int tmp = v[i] + knapSack(wt - w[i]);
        if (tmp > maxValue){
            maxValue = tmp;
            vtemp = v[i];
            wtemp = w[i];
        }
    }
    System.out.println("wt="+wt + ",vtemp="+vtemp+",wtemp="+wtemp+",ret max="+maxValue);
    return maxValue;
}

だから私の質問は：

  1. 引数に n が必要なのはなぜですか?
  2. ステートメント if (s[n] > W) result = Value(n-1,W); 理由を理解するのをさらに難しくする
  3. 私のアプローチのメモ化されたバージョンでも、同じ大きな O が表示されます。他に違いはありますか？

ありがとう。

4

1 に答える 1

0

あなたは実際には別の問題を解決しています。コードの最初の部分 ( を使用n) は0-1 ナップザック問題を解決します。この問題では、特定のアイテムを最大 1 つ選択できます (つまり、アイテムの「コピー」はありません)。その場合、nすでに使い切ったアイテムを追跡する必要があります。

コードの 2 番目の部分では、無制限のナップザック問題を解きます。この問題では、すべてのアイテムを無制限に取ることができます。

どちらも NP 完全ナップザック問題の形式ですが、解が異なります。

于 2013-08-20T02:47:51.523 に答える