[請益] 0/1 knapsack problem的遞迴式
看板Prob_Solve (計算數學 Problem Solving)作者mqazz1 (無法顯示)時間14年前 (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
→
07/27 19:25, , 1F
07/27 19:25, 1F
→
07/27 19:26, , 2F
07/27 19:26, 2F
推
07/29 01:00, , 3F
07/29 01:00, 3F
→
07/29 01:01, , 4F
07/29 01:01, 4F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
