正確な必須項目番号制約を伴うナップザック問題

Question

ナップザックの問題を定数 $ l $ で修正する必要がある場合、ナップザックの問題を解決するのでしょうか。これは同じ問題です（ $ w $ の最大重み、すべての項目に値 $ v $ があります。重み $ w $ ）ですが、を $ l $ 項目を追加する必要があります。ナップザックへの（そして明らかにナップザックの合計値を最適化する必要がある）。

これまでにこれを実装することを考えたあらゆる方法（動的計画法、ブルートフォース）は故障、または宇宙レベルの計算時間のいずれかをもたらしました。あらゆる助けやアイデアが高く評価されています。

編集：疑似多項式タイムソリューションを探しています

Answer 1

この問題をナップザックのインスタンスに変換することができます。 $ n $ をアイテムの数、 $ v $ 項目の最大値になり、してください。各項目の重さは、ほとんどの $ w $ （そうでなければ破棄される可能性があります）。

少なくとも $ l $ 項目を選択することを確認するため：

• $ n（v + 1）$ をすべての項目の値に追加します。
• 今問題は、選択されたアイテムの数を最大化することと同等であり、重みの制約の対象となる、最大の元の合計値を持つアイテムのセットを支持していることと同等です。最適なソリューションの場合、少なくとも $ l $ 項目が少なくとも $ n（v）の値を選択する解決策があります。 +1）L $ 。

必ず $ l $ 項目：

• $（w + 1）$ をすべてのアイテムの重みに追加します。
• 追加 $ l（w + 1）$ $ w $ 。
• $ l $ 項目すべてのサブセットは、少なくとも $（l + 1）（w + 1）です。 ）= L（w + 1）+（w + 1）> L（w + 1）+ w $ 、したがって実現不可能です。 $ l $ のすべてのサブセット $ w $ の重みを持ち、 $ L（W + 1）+ W $ 、したがって、実現可能なIFF $ w \ lew $ です。 $ l $ 項目以外のサブセットは、その全体の重みが $ w $ しかし、その合計値は常に $ n（v + 1）l $ よりも小さくなります。