algorithm - ナップザックのバリエーション - 「W」を超える最小合計値

Question

n重みと値を使用して、通常のアイテムのセット (それぞれ無制限など) を考えると、次のようになります。

w1, v1
w2, v2
...
wn, vn

と目標重量、総重量が少なくとも、合計値が最小にWなるような項目を選択する必要があります。 W

これは、整数/無制限のナップザック問題のバリエーション (またはある意味ではその逆) のように思えます。DP アルゴリズムの定式化の助けをいただければ幸いです。

Answer 1

しましょうTOT = w1 + w2 + ... + wn。

この回答では、2番目のバッグについて説明します。オリジナルは「バッグ」、追加は「ナップサック」と表記します。

バッグにすべての要素を入れ、要素を除外し始めます。可能な限り高い値で、最大でサイズの新しいナップザックを「いっぱいにします」。TOT-W同じ要素とバッグサイズの通常のナップサック問題が発生しましたTOT-W。

証明：
k個の要素を持つ最良の解決策があると仮定します：e_i1,e_i2,...,e_ik、その場合、バッグのサイズは少なくともサイズWであり、除外されたアイテムは最大でサイズでナップザックになりますTOT-W。また、ナップザックの値はサイズWに対して最小化されているため、除外されたアイテムの値はサイズに対して最大化されます。最大化さTOT-Wれていない場合は、少なくともサイズのより良いバッグがあり、W値が小さいためです。
逆の方法[最大の除外バッグがあると仮定]はほとんど同じです。

Answer 2

確かではありませんが、これはうまくいくかもしれません。値は、あなたが持っている値の -ve であると考えてください。DP の定式化は、この場合、最小の負の値となるその重みの最大値を見つけようとします。値が得られたら、最終的な答えとして -ve を取ります。