0

すべてのアイテムには 3 つのプロパティがあります

  • アイテムのサイズ S i
  • 項目 V iの値
  • アイテムをナップザックに追加するために必要な最小値 M i (<= 10 7 )

最大で 100 アイテムになります。

ナップザックのサイズ K (K <= 1000) と初期値 V (ナップザックにスペースを取りません) が与えられます。M iが V 以下
の場合にのみ、項目「i」をナップザックに入れることができます。ナップザックに項目を追加した後、V は V iだけ増加します。特定のサイズのナップザックに入れるアイテムの数 (値ではない) を最大化する必要があります。

同様のこの質問を見つけました。しかし、答えで説明されているアルゴリズムは立方時間であり、この問題には十分に高速ではありません。より良い方法でこの問題に取り組むにはどうすればよいでしょうか?

4

1 に答える 1

1

ここで O(n^3) アルゴリズムを提供できます。この質問をさらに O(n^2) に最適化できるかどうかはわかりません。

まず、この問題は if アイテムの数を最大化する問題であり、他のナップザックの問題とは少し異なります。一方、ナップザックの合計値がそれ自体の値よりも大きい場合にのみ、単一のアイテムを選択できるという制限もあります。したがって、明らかな推論は、同じ数のアイテムが選択され、合計サイズが固定されている場合、合計値はできるだけ大きくする必要があります (より多くのアイテムをナップザックに追加できるようにするため)。

アイテムの数 n(<=100) とナップザックのサイズ K(<=1000) はそれほど大きくないことに注意してください。f[i][j] は、合計サイズ j の i 個のアイテムを選択したときの最大値を意味します。最初に、f[0][0]=V を除くすべての f[i][j] が 0 に設定されます。

次に、追加に必要な最小値に基づいて項目を並べ替えます。これは貪欲な考え方です。なぜなら、ソート後、各項目を 1 回しか調べられないからです。

DP メソッドは次のようになります。

for (int k=0;k<n;k++) //iterate items
    for (int i=n;i>=0;i--)
        for (int j=K;j>=0;j--) if (item.M[k]<=f[i][j])
            f[i+1][j+item.S[k]]=max(f[i+1][j+item.S[k]],f[i][j]+item.V[k]);

そして最終的な答え（アイテムの最大数）は次のとおりです。

for (int i=n;i>=0;i--)
    for (int j=0;j<=K;j++)
        if (f[i][j]) return i;
于 2013-04-01T03:28:55.213 に答える