[理工] 102交大資結演算

看板Grad-ProbAsk作者 (tanece)時間12年前 (2014/02/09 01:39), 編輯推噓6(6推 0噓 19→)
留言25則, 8人參與, 最新討論串1/1
想問15、17、18題 http://miupix.cc/pm-72HPR2 http://miupix.cc/pm-F3BZ25 17題是類似原文書constraint graph用Johnson's algo做嗎？ 然後求出xi都<=0的max? 15、18就看不太懂 麻煩大家了 另外有人有上題庫班有其它題的答案嗎？ 想對9、10、14的答案 手機排版請見諒 -- Sent from my iPhone -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 119.77.169.95
→
02/09 01:51, , 1F
17題我xi分別是-4、-2、0、-1、-3，ans=-10 有誤請指正
02/09 01:51, 1F
推
02/09 09:55, , 2F
我跟樓上一樣 我是用greedy求出來的
02/09 09:55, 2F
→
02/09 10:06, , 3F
18.有點類似霍夫曼吧，我是用GREEDY。
02/09 10:06, 3F
推
02/09 10:40, , 4F
17求maximum不是無限大嗎？
02/09 10:40, 4F
→
02/09 10:49, , 5F
xi<=0 所以最大不可能超過0 用greedy反而更快 同1樓
02/09 10:49, 5F
→
02/09 10:50, , 6F
18 關鍵"最大權值一定在最底層"
02/09 10:50, 6F
→
02/09 10:55, , 7F
想請問一下用greedy算的過程 不太會
02/09 10:55, 7F
→
02/09 11:07, , 8F
式子分別1~8 先設xi全0 但不滿足2,6,7 由於6,7跟x3有關
02/09 11:07, 8F
→
02/09 11:08, , 9F
且x3變小只會越蹧 所以固定0 設x4=-1,x5=-3滿足6,7 回
02/09 11:08, 9F
→
02/09 11:08, , 10F
到式子2由於x5=-3 所以x4=-1再檢查一次 3不滿足 因此設
02/09 11:08, 10F
→
02/09 11:09, , 11F
x2=-2 最後檢查ok
02/09 11:09, 11F
→
02/09 11:10, , 12F
打反了 回到式子2 x1是-4 其他過程不變
02/09 11:10, 12F
推
02/09 14:14, , 13F
18題我算6 有人找到更小的嗎
02/09 14:14, 13F
→
02/09 14:57, , 14F
6怎算的…我關鍵字很明顯吧==6個點要當成葉子所以就是
02/09 14:57, 14F
→
02/09 14:58, , 15F
變形huffman而已 應該是75/32吧
02/09 14:58, 15F
推
02/09 15:34, , 16F
看錯 沒注意到都當葉子，可分享一下畫出的bt嗎？我算不出
02/09 15:34, 16F
→
02/09 15:53, , 17F
會建huffman吧 5,6在底層 往上 依序4,4,3,2
02/09 15:53, 17F
→
02/09 15:53, , 18F
至於b的證明 其實就類似huffman證法 就不講了 去翻書吧
02/09 15:53, 18F
推
02/09 16:07, , 19F
http://miupix.cc/pm-9P5Z6R 我是這樣畫 算91/32 75/32
02/09 16:07, 19F
→
02/09 16:07, , 20F
是你把root 高當1？題目說當0
02/09 16:07, 20F
→
02/09 16:11, , 21F
沒 你算對了 我不小心把2*(1/2)算成=1/2 少加16 XD
02/09 16:11, 21F
→
02/09 16:14, , 22F
因為沒補題庫 100後考古全部都自己寫==雖然朋友有補XD
02/09 16:14, 22F
→
02/09 16:14, , 23F
說洪逸沒整理 都放章節 乾脆自己寫一份…
02/09 16:14, 23F
推
02/09 16:15, , 24F
了解XD 感謝ki大
02/09 16:15, 24F
→
02/10 10:39, , 25F
題目說的optimal value是全部加起來唷==?
02/10 10:39, 25F
‣ 更多 tanece 的文章
文章代碼(AID): #1IzclERC (Grad-ProbAsk)