algorithm - 最小コストのナップザック

Question

私はいくつかの種類のコインを持っています、それぞれが重量（wi）とコスト（ci）を持っています。だから私はweight==Wと（！）コインの最小コストでナップザックを作らなければなりません。DPを使用するための漸化式を作成できません。

Answer 1

通常の漸化式を定式化するだけです...

総重量kで達成可能な最小コストをMin_cost（k）として指定します。

次のコマンドでメモ化をブートストラップします。

Min_cost(0) = cost of empty set = 0

次に、以下を使用してkの値の増加を解きます。

Min_cost(i+1) = min [Min_cost(i)   + min [ci, for all items with wi = 1],
                     Min_cost(i-1) + min [ci, for all items with wi = 2],
                     Min_cost(i-2) + min [ci, for all items with wi = 3],
                     ...
                     Min_cost(2) + min [ci, for all items with wi = w-1],
                     Min_cost(1) + min [ci, for all items with wi = w],
                     Min_cost(0) + min [ci, for all items with wi = w+1]]