作者mqazz1 (无法显示)
站内Prob_Solve
标题[请益] 0/1 knapsack problem的递回式
时间Tue Jul 27 19:19:28 2010
0/1 knapsack problem
令 c[i,k] 为当可负重k，并可以拿物品1,2,...,i，所获得的最高价值
c[i,k] = 0 if i=0 or k=0
c[i-1, k] if wi > k
Max( vi + c[i-1, k-wi], c[i-1, k] ) if k >= wi
取0个物品或可负重0 价值就是0
当item i的重量超过可负重的重量时，价值就是item 1~ item i的加总
但我不太懂 k>=wi 的式子..
能不能请高手指点一下
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.28.142
1F：→ tkcn:w_i > k 表示已经拿不动第 i 个了，所以直接考虑下一个 07/27 19:25
2F：→ tkcn:咦，原来是问另一行。 那就是分别考虑拿与不拿两种情况的价值 07/27 19:26
3F：推 mavewei:如果i的重量小於可负重K，就取两值里面的最大值。 07/29 01:00
4F：→ mavewei: 或等於 07/29 01:01