PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 數值合併

看板Prob_Solve (計算數學 Problem Solving)作者march20時間18年前 (2006/07/09 02:28)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/15 (看更多)

※ 引述《windows2k (KERORO軍曹)》之銘言： : 版上強者很多, 所以我又來問問題了 : 有一系列的數字, 每次挑兩個相鄰的數字合併 : 合併的數字按照原來順序插入序列之中, 合併的代價為 s , s 為兩個數字的和 : 經過一連串的合併之後, 整個序列會只剩下一個值, 而總合併代價為 S : 問怎樣的合併動作, 總合併代價會是最小 : 範例一: : 3 4 5 (3,4) 合併代價 7 : 7 5 (7,5) 合併代價 12 : 12 總代價 19 : 範例二: : 5 3 4 5 (5,3) 合併代價 8 : 8 4 5 (4,5) 合併代價 9 : 8 9 (8,9) 合併代價 17 : 17 總代價 34 : 5 3 4 5 (3,4) 合併代價 7 : 5 7 5 (5,7) 合併代價 12 : 12 5 (12,5) 合併代價 17 : 17 總代價 36 : 可見greedy algorithm並非最佳解 : 用Dynamic programming的話, 存在一個 O(n^3)的演算法 : 不過有一個 O(nlogn)的演算法, 卻不得其門而入看到 n log n , 大膽猜看看. 給定數列 S = {s_1, s_2, s_3, ... , s_n} 先造一個 L[0..n], 其中 L[x] = sum_{1<=i<=x} s_i 這樣就可以簡單地求到任意一組 s_x + ... + s_y = L[y] - L[x-1]. 接下來 divide and conquer: 假設要求 s_x, ... , s_y 的最佳合併, 採 binary search 找出 s_x,...,s_y 的中位點 s_m 也就是 mid = [sum_{x<=i<=y} s_i]/2 的值落在 s_m 上. urr, 簡單來說 (!?), 也就是 [sum_{x <= i <= m-1} s_i] < mid <= [sum_{x <= i <= m} s_i] 我猜最佳合併法就是 s_x,...,s_m 和 s_(m+1),...,s_y 先各自合併, 接著再併起來. (s_m 要歸在左還是右, 似乎沒那麼簡單, 好像要看怎麼分兩邊和的差最小?) 還沒驗證過, 先 post 出來 XD. : 有誰可以提示一下, 感激不盡 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 71.137.22.103