[理工] [DS] 100中央

看板Grad-ProbAsk作者 (阿蛋)時間12年前 (2012/02/11 20:11), 編輯推噓3(3推 0噓 15→)
留言18則, 3人參與, 最新討論串1/3 (看更多)
http://rapid.lib.ncu.edu.tw:8080/cexamn/exam/EC02_100_01.pdf 想請問第六題的upper bound跟lower bound到底要怎麼算呢 ?? 書看了好久還是霧煞煞... 麻煩各位幫忙一下>"< 謝謝!! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 1.169.124.147
推
02/11 20:16, , 1F
Branch and Bound洪捷書上不是有 我嚴重懷疑中央100
02/11 20:16, 1F
→
02/11 20:16, , 2F
是他出的
02/11 20:16, 2F
→
02/11 20:17, , 3F
他的Bound就用fraction 背包問題去bound
02/11 20:17, 3F
推
02/11 20:20, , 4F
觀念在於我用KP的取法都取不贏你現在展開的node
02/11 20:20, 4F
→
02/11 20:20, , 5F
那那個節點就不用展開了
02/11 20:20, 5F
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)
推
02/11 20:46, , 6F
你要先把他對 Vi/Wi 排序
02/11 20:46, 6F
→
02/11 20:47, , 7F
物品取法按照 價物比排好 W=4
02/11 20:47, 7F
→
02/11 20:48, , 8F
現在的Item1 是原本Item3 新I2為原本I2 新I3為原I1
02/11 20:48, 8F
→
02/11 20:49, , 9F
你走右邊代表你新I1不取 那I2,I3照KP取
02/11 20:49, 9F
→
02/11 20:50, , 10F
W=4>W2=2所以全取 然後 W3=3所以你只能取2
02/11 20:50, 10F
→
02/11 20:51, , 11F
所以價值就是 10+(2/3)*12=18
02/11 20:51, 11F
→
02/11 20:52, , 12F
像左邊那個 你已經取I1了 所以CurrentValue=6
02/11 20:52, 12F
→
02/11 20:53, , 13F
I2,I3一樣用KP取 你現在W剩3 所以I2可以全取 I3只能取1
02/11 20:53, 13F
→
02/11 20:53, , 14F
所以Bounding值=6+10+(1/3)*12=20
02/11 20:53, 14F
→
02/11 21:45, , 15F
謝謝QQ
02/11 21:45, 15F
→
02/11 21:46, , 16F
所以upper和lower是取最大和最小值嗎??
02/11 21:46, 16F
→
02/11 21:51, , 17F
就是算出來的每個NODE的VALUE嗎??
02/11 21:51, 17F
→
09/11 14:55, , 18F
你要先把他對 Vi/W https://daxiv.com
09/11 14:55, 18F
‣ 更多 Eggchun 的文章
文章代碼(AID): #1FDbhkHa (Grad-ProbAsk)
‣ 更多 Eggchun 的文章
文章代碼(AID): #1FDbhkHa (Grad-ProbAsk)