背包以最小的成本(Knapsack with minimum cost)

我有几个类型的硬币，各有重量（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]]

文章来源: Knapsack with minimum cost