algorithm - 最低成本的背包

Question

我有几种类型的硬币，每种都有重量（wi）和成本（ci）。所以我必须制作一个重量==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]]