最低成本的背包

我有几种类型的硬币，每种都有重量（wi）和成本（ci）。所以我必须做一个背包，重量== W和（！）硬币的最低成本。我不能让使用DP的复发关系。最低成本的背包

2013-03-17 user2178460

你的意思是你被允许做的关系？ – 2013-03-17 03:23:08

我必须做一个关系，或者如何在没有它的情况下使用DP？ – user2178460 2013-03-17 03:25:26

就制定通常递推关系...

标明用总重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]]

来源

2013-03-17 04:32:21

如果没有当前wi的元素，在这种情况下如何找到min [ci，对于wi = 1的所有项目]？例如W = 100和2种类型的项目：w1 = 1 c1 = 1; w2 = 50 c2 = 30，所以这里的答案应该是60，我不能用你的算法得到它。你能更好地解释你的想法吗？ – user2178460 2013-03-17 07:51:39

如果没有wi = 1的项目，那么对于重复中所有wi = 1行的项目，您不能拥有Min_cost（i）+ min [ci，因为这些项目不存在。至于相同类型的多个硬币，每个硬币的数量是多少？因为Min_cost（50）= min [Min_cost（49）+ c1，Min_cost（0）+ c2），直到你计算Min_cost（50），此时它将切换到c2， ] = min [49 + 1,0 + 30] = 30'。在W = 90时，你会得到Min_cost（100）= 60。顺便说一下，这看起来像一个算法分配...希望你没有使用StackOverflow作业:) – 2013-03-17 08:04:56

好吧，现在已经很清楚了。谢谢。 – user2178460 2013-03-17 08:14:32

最低成本的背包

回答

相关问题