[請益] 0/1 knapsack problem的遞迴式

[mqazz1 (無法顯示)]

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
→ tkcn:w_i > k 表示已經拿不動第 i 個了，所以直接考慮下一個
→ tkcn:咦，原來是問另一行。 那就是分別考慮拿與不拿兩種情況的價值
推 mavewei:如果i的重量小於可負重K，就取兩值裏面的最大值。
→ mavewei:               或等於