作者jacksoncsie (Nov)
看板Grad-ProbAsk
標題[理工] 108交大資演 23小題
時間Sat Dec 25 00:48:55 2021
https://i.imgur.com/3qPTUj3.jpg
https://i.imgur.com/EzJ47yM.jpg
問這題，前情提要答案是 D
而原題答案 X = 91
(4 + 4) + 8 + (5 + 4) + (3 + 5)
= (8 + 8) + (9 + 8) = (16 + 17)
→ 8 + 9 + 8 + 16 + 17 +33 = 91
我是想問演算法實作的部分，
看之前上討論只說可以用 matrix chain 類似方式去求解，
而 matrix chain 最快可在 O(n lg n )下實作
該篇算法
http://i.stanford.edu/pub/cstr/reports/cs/tr/81/875/CS-TR-81-875.pdf
以下是我的想法 :
Find_Small_Intermediate_Sum(int *list, int list_size)
Sequential search list, determine the total size is odd or even
if(list_size % 2 == 0){
Divide the list into group, which group size is 2
Calculate the sum for the each group, put it into the list
Find_Small_Intermediate(list, list_size / 2)
}else{
list \ the biggest one // Don't calculate the biggest one
Divide the list into group, which group size is 2
Calculate the sum for the each group, put it into the list
Find_Small_Intermediate(list, list_size / 2)
}
# 演算法步驟
1. Split the list // O(log n)
2. 判斷總數為何 若為基數 先去除最大項, 偶數不變 // O(n)
3. 接下來依剩下儲存值與相臨數值相加之後 merge // O(n)
有問題歡迎指證 感恩
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.37.48.158 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1640364537.A.7E0.html
※ 編輯: jacksoncsie (114.37.48.158 臺灣), 12/25/2021 01:03:47
推 FRAXIS: 你假設 list size 是 2 的次方數.. 12/25 12:46
→ FRAXIS: 你的方法會考慮最佳解是先加第二元素和第三個嗎? 12/25 12:48
→ FRAXIS: 感覺你的方法不會認定第二個和第三個元素會相鄰 12/25 12:49
→ jacksoncsie: F大你好，之前也是看你有回復同樣問題才想上來問的 12/25 13:17
→ jacksoncsie: 第3項由於是最大值，且總數是基數所以我打算先 12/25 13:19
→ jacksoncsie: 不加此項，有點像merge sort判斷說如是基數項，則直 12/25 13:20
→ jacksoncsie: 接mapping到下階段的陣列 12/25 13:20
→ jacksoncsie: 而關於演算法實作的部分，我是有2個準則 12/25 13:21
→ jacksoncsie: 我的樹大概畫成這樣 12/25 13:27
→ jacksoncsie: root 是 33 寫錯 12/25 13:28
→ mathtsai: 這題一臉dp（？） 12/26 11:55
推 FRAXIS: 這題如果是用 DP, 你可以很容易說明為什麼所有可能 12/27 11:51
→ FRAXIS: 都會被考慮到 最基本的形式會是 O(n^3) 時間複雜度 12/27 11:51
→ FRAXIS: 如果要加速 你必須要說明你節省的地方是不可能會有最佳解 12/27 11:52
→ jacksoncsie: 了解 之前看討論也是說用DP 不過我這感覺像Greedy 12/27 22:21
→ jacksoncsie: 霍夫曼樹的變形 :( 12/27 22:21