最低成本的背包
就制定通常递推关系...
标明用总重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]]
如果没有当前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。顺便说一下,这看起来像一个算法分配...希望你没有使用*作业:) – 2013-03-17 08:04:56
好吧,现在已经很清楚了。谢谢。 – user2178460 2013-03-17 08:14:32
你的意思是你被允许做的关系? – 2013-03-17 03:23:08
我必须做一个关系,或者如何在没有它的情况下使用DP? – user2178460 2013-03-17 03:25:26