作者hank1321 (knah1321)
看板Grad-ProbAsk
標題[理工] 108交大資演
時間Mon Feb 18 18:29:08 2019
想問一題minimal intermediate sum的
好像是第21題，題組題
題目大概是說，4+1+2+3可以插入3組括號變成((4+1)+(2+3))=((5)+(5))=10 然後5+5+10=
20
但也可以寫成(4+((1+2)+3)) 會跑出3,6,10,sum=19
19就比20小
然後問題是要找4,4,8,5,4,3,5的最小解
我算是
(((4+4)+8)+(5+((4+3)+5)))
=(((8)+8)+(5+((7)+5)))
=((16)+(5+(12)))
=(16+(17))
=(33)
分別跑出8,7,16,12,17,33，相加起來是93
可是答案好像是給91
不知道自己盲點到底在哪裡...
有大大可以提供一下解出91的想法嗎 感恩
一題就整題組爆 好痛嗚嗚
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.92.113
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1550485751.A.557.html
1F：→ h3882249: 用哈輔慢呢 02/18 18:35
2F：推 cks116: 4+4 8 5+4 3+5 02/18 18:36
3F：→ cks116: 我是想讓局部盡量小 且數大小平均一點 02/18 18:37
4F：推 magic83v: 用huffman作法 02/18 18:37
5F：推 skyHuan: 那時候想好久是Huffman還是像matrix chain那樣還是想不出 02/18 18:50
6F：→ skyHuan: 來QQ 02/18 18:50
7F：推 Dora5566: 不能huffman吧 最小的兩個又不一定相鄰 02/18 18:54
8F：推 aeiou335: 要用dp 02/18 18:57
9F：推 eric21489: 同2樓作法 這樣91沒錯 我忘了加最後一次... 02/18 18:57
10F：推 ko330: 第二行5跟5合阿 就是用ㄏ夫曼= = 02/18 18:59
11F：推 ChunagMT: 我以為數字不能對調… 02/18 19:05
12F：推 uttc: 也想知道91怎麼出來的 02/18 19:11
13F：推 eric21489: 8+9+8+16+17+33 02/18 19:12
14F：推 ruifan: 不是插括號 可以任選兩個加 02/18 19:14
15F：推 ruifan: 題目沒有說要相鄰吧 02/18 19:16
16F：→ S2067030: 現場完全來不及做 在家算的方法跟2樓一樣 02/18 19:16
17F：→ eric21489: 我覺得不能動吧 02/18 19:18
18F：推 ruifan: 等等 我又看了一次題目 好像是插括號沒錯 02/18 19:18
19F：→ eric21489: 只是剛好huffman答案一樣就是了 02/18 19:20
20F：推 maple205: 不能換位置吧 02/18 19:23
21F：推 cvn21: 這題就是霍夫曼啦 02/18 19:42
22F：推 ChunagMT: 不能換位子答案還會一樣嗎？ 02/18 19:43
23F：推 YeaPa: 2樓應該是對的 我現場也是算93 QQQ 02/18 19:45
24F：→ S2067030: 題目是4.4.8.5.4.3.5 02/18 19:56
25F：→ S2067030: (((4+4)+8)+ ((5+4)+(3+5))) 02/18 19:57
26F：→ S2067030: 8+9+8+16+17+33=91 02/18 19:57
28F：→ f101202: 題目應該讓霍夫曼出來的答案不一樣..這樣就被某些人撿到 02/18 20:45
29F：→ f101202: 了== 02/18 20:45
30F：推 magic83v: 真的==撿到一題 那個turnaround time*4也撿到 02/18 21:46
31F：推 Dora5566: 辣基= = 02/18 23:48
32F：噓 Dora5566: 不知道多少人用huffman賺分 02/18 23:52
33F：推 uttc: 這用赫夫曼的話第一步是3+4 不會對 例如我QQ 02/19 00:50
34F：→ f101202: 這運氣真的有點屌..錯錯得正 02/19 02:11
35F：→ uttc: 哦 原來是偷換了位子會對.... 02/19 02:12
36F：→ gaowei16: 沒說不能換吧== 02/19 08:18
37F：→ gaowei16: 不過我沒換算91 第二次算81 直接失智 02/19 08:19
38F：→ gaowei16: 喔對 剛剛又看了一下 不能換 答案真根霍夫曼一樣== 02/19 08:23
39F：推 skyHuan: 霍夫慢到底怎麼選，我一開始用霍夫曼想沒辦法選點就用DP 02/19 08:44
40F：→ skyHuan: 了，但試了一下覺得太麻煩就跳過最後來不及用猜的>< 02/19 08:44
41F：推 f101202: Sky葛格錯誤的方法不要學>\\\\< 02/19 11:28
42F：推 ekids1234: 抱歉借串問，資演有一題算 array memory address 的， 02/19 13:10
43F：→ ekids1234: 大家都算的跟解答一樣？人在外沒帶考卷 02/19 13:10
44F：→ Dora5566: 樓上 一樣 02/19 13:33
45F：→ hank1321: 一樣 02/19 14:14
46F：推 Rioronja: 用dp解 02/19 16:14
48F：→ ekids1234: 想詢問一下我想錯了哪邊 QQ 02/19 19:45
49F：推 young60509: 跟ekid大一樣寫E 不懂為啥錯QQ 02/19 20:54
50F：→ uttc: 題目要16進位 68是10進位 02/19 21:06
51F：推 tinhanho: f大的DP 1,4 是42吧 12/24 21:29
52F：推 tinhanho: 1,6 是71吧 12/24 21:35