推 pikachu123:Branch and Bound洪捷書上不是有 我嚴重懷疑中央100 02/11 20:16
→ pikachu123:是他出的 02/11 20:16
→ pikachu123:他的Bound就用fraction 背包問題去bound 02/11 20:17
推 pikachu123:觀念在於我用KP的取法都取不贏你現在展開的node 02/11 20:20
→ pikachu123:那那個節點就不用展開了 02/11 20:20
Item Wi Vi
1 3 12
2 2 10
3 1 6
$0
0kg
20
／ ＼
$6 $0
1kg 0kg
20 18 <---想請問18是怎麼算出來的>"<
／＼
※ 編輯: Eggchun 來自: 1.169.124.147 (02/11 20:42)
推 pikachu123:你要先把他對 Vi/Wi 排序 02/11 20:46
→ pikachu123:物品取法按照 價物比排好 W=4 02/11 20:47
→ pikachu123:現在的Item1 是原本Item3 新I2為原本I2 新I3為原I1 02/11 20:48
→ pikachu123:你走右邊代表你新I1不取 那I2,I3照KP取 02/11 20:49
→ pikachu123:W=4>W2=2所以全取 然後 W3=3所以你只能取2 02/11 20:50
→ pikachu123:所以價值就是 10+(2/3)*12=18 02/11 20:51
→ pikachu123:像左邊那個 你已經取I1了 所以CurrentValue=6 02/11 20:52
→ pikachu123:I2,I3一樣用KP取 你現在W剩3 所以I2可以全取 I3只能取1 02/11 20:53
→ pikachu123:所以Bounding值=6+10+(1/3)*12=20 02/11 20:53
→ Eggchun:謝謝QQ 02/11 21:45
→ Eggchun:所以upper和lower是取最大和最小值嗎?? 02/11 21:46
→ Eggchun:就是算出來的每個NODE的VALUE嗎?? 02/11 21:51