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

看板Prob_Solve作者mqazz1 (無法顯示)時間15年前 (2010/07/27 19:19)推噓1(1推 0噓 3→)

留言4則, 2人參與討論串1/1

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

07/27 19:25, , 1^F

07/27 19:25, 1^F

→

tkcn

07/27 19:26, , 2^F

07/27 19:26, 2^F

推

mavewei

07/29 01:00, , 3^F

07/29 01:00, 3^F