逆ナップザックの問題

Question

私は次のタスクを解決しようとしています： それぞれが重みと値を持つアイテムのセットを与えられた場合、与えられた合計値のナップザック最小運搬容量を決定します。

item1: w = 3.4, v = 3 
item2: w = 0.4, v = 1 
total value = 7 

出力：

我々が取るべき：

item1 x0, item2 x7 

そして

minimal capacity = 0 * 3.4 + 0.4 * 7 = 2.8 
total value = 7 

再帰何式はIべき例 入力の場合

動的プログラミングを使用する一般的なアルゴリズムに使用しますか？誰も小さな入力データでこれを解決する例を見せてもらえますか？

P.S.私の英語のために申し訳ありません。

Answer 1

従来の（最大化する）ナップザックアルゴリズムは正常に動作するはずです。ちょうどmaxの出現をすべてminに入れ替えれば、ほぼそこにいるはずです。これを見るもう1つの方法は、負のコストを使用しているため、最小化が最大になります（空のケースに特別な注意を払う必要があります）。