ナップザック：1つの制約、各アイテムは多数のアイテムで1回のみ選択できます

Question

ナップザック問題フォームを採用したアルゴリズムを書いています。最大の体重（W）を与えられたナップザックの価値（V）を最大限にしようとしています。キャッチは、各アイテム（I）は1回のみ選択でき、重さにかかわらずナップザックは10アイテムしか保持できず、非常に多数のアイテム（500+）があることです。

これまでのところ、過体重であるナップザックを生成して、一度に1つずつ逆順に作業して、< =最大の重みになるようにしました。これは最適なナップザックを生成するための問題ではありませんが、次のような100種類のナップザックを生成したいと思います。私は私の再帰的プロセスを続けることによってこれを行うことができると考えていたが、ちょっと最適なナップザックが欠けている可能性があるので、これは完全に正確であるとは思わない。

Answer 1

この問題は、整数プログラムとして公式化することができます。

maximize sum_{i in items} v_i * x_i 
subject to 
sum_{i in items} x_i <= 10  [u] 
sum_{i in items} w_i * x_i <= W [z] 
for all i in items, x_i in {0, 1} [y_i] 

このプログラムを解決する多くのソルバーライブラリがあります。代わりに、あなた自身branch and boundを行うことができます。ここでは、分岐と結合に必要な整数プログラムの目的関数値の上限を得るために解くことができる二重線形プログラムがあります。 zの値が与えられる

minimize 10 * u + W * z + sum_{i in items} y_i 
subject to 
for all i in items, u + w_i * z + y_i >= v_i [x_i] 
u >= 0 
z >= 0 
for all i in items, y_i >= 0 

、他の変数を設定する第十の最大値にuを割り当てる際v_i - w_i * zによって9つのトップ項目に正y_iを割り当てるの問題です。時刻O(n log n)には、zの3進検索が可能です。