Re: [問題] 請問有關鋸木問題寫成程式比較快的方法

看板Programming作者king19880326 (OK的啦～我都可以接受)時間16年前 (2009/04/29 16:48)推噓1(1推 0噓 4→)

留言5則, 1人參與討論串3/3 (看更多)

※ 引述《king19880326 (OK的啦～我都可以接受)》之銘言： ※ [本文轉錄自 C_and_CPP 看板] 作者: king19880326 (OK的啦～我都可以接受) 看板: C_and_CPP 標題: [問題] 請問有關鋸木問題寫成程式比較快的方法時間: Mon Apr 27 08:51:15 2009 /*** 這是引文 ******** *題目敘述如下 * *有一個木頭, 長度是 L, 假設位於座標 (0, L)中間, 現給 n 個點 p1, p2...pn * *0 <= pi <= L (1 <= i <= n). 希望可以將原本的木頭切成這 n+1 段 * *現在定義切木頭的cost如下 : 如果木頭長度是 L1, 則切此木頭的 cost 就是L1 * *(不論切在哪一個點). 試問該用何種順序才能使得切出這 n+1 段的 cost 為最小 * * 舉例: * * 假設木頭位於 (0, 9) 要切的 3 個點分別為 3, 4, 8 * * 則如果由右往左切 cost 為 9(0 -> 9 中切 3 這個位置) + 6(3 -> 9中切 4 這 * * 個位置) + 5(4 -> 9中切 8 這個位置) = 20 * * 如果是由左往右切 cost 為 9(0 -> 9 中切 8 這個位置) + 8(0 -> 8中切 4 這 * * 個位置 + 4(0 -> 4中切 3 這個位置) = 21 * *我的想法如下 : * *定義 P(i,j) 為 (1 <= i <= n, 1 <= j <= n) 為切第 i 刀時, 所切的位置在 * *j 的 cost 最小. * *以下是一個簡單的觀察 : min{P(n,1), P(P,2), ... P(n,n)} = 所求 * *(因為共要切 n 刀, 而第 n-1 刀有可能是切在 p1, p2, ...pn 這 n 種可能) * *P(i, j) = min{P(i-1,1) + 切在 j 的代價, P(i-1, 2) 切在 j 的代價, ...P(i-1,n) * * + 切在 j 的代價} (令P(i-1,j) = 負無限大) * *P(1, j) = L (1 <= j <= n) * *因此用 DP 填表格的方式共 n * n 格要填 * *填每一格需要的時間複雜度為 O(n) * *所以時間複雜度是 O(n^3) * *這樣的時間複雜度好像有點高 @@>, 請問有什麼方法可以把它的時間複雜度往下降嗎?? * *感謝感謝 * *****引文結束*******/ 自問自答一下 <(__)> 就像bobju 大大的說法, 之前的 P(i, j) = min{P(i-1,1) + 切在 j 的代價, P(i-1, 2) 切在 j 的代價, ...P(i-1,n) + 切在 j 的代價} (令P(i-1,j) = 負無限大) 這個式子並不保證每一格可以在 O(n) 填入. 事實上我也還沒想到簡明的方法去 implement(希望版友如果有想到可以提供 <(__)>) 如果我們從另外一個方向去做 DP, 似乎就顯得好處理多了方法如下: 假設 input 的長度是 20, 共切 4 刀, 切在 2, 6, 8, 16等處 (將位置排序, O(nlogn)) 之前是從"刀數"去做DP, 現在改從"段"去做DP 所以我們可以把整個木頭看成如下這個圖: ___________________ |___|___|___|___|___| 0 2 6 8 16 20 \ / \ / \ / \ / \ / 1 2 3 4 5 <-這是將每"段"木頭編號我們定義 cut_left[i] = 第 i 段木頭的左端點 ex. cut_left[1] = 0, cut_left[2] = 2,...cut_left[5] = 16 (O(n)) cut_right[i] = 第 i 段木頭的右端點 ex. cut_right[1] = 2, cut_right[2] = 6,...cut_right[5] = 20 (O(n)) 且定義 C[i,j] 為 i, i+1, ...j-1, j 這段木頭切割所需要的最小 cost 現在我們可以有兩個簡單的觀察: 1. C[1,n+1] = 所求 (n 為共需要切割的刀數) 2. C[i,j] = min{ C[i,i]+C[i+1,j], C[i,i+1]+C[i+2,j]...,C[i,j-1]+C[j,j] } + cut_right[j] - cut_left[i] (註1) (if i < j) => min{ C[i,k]+C[k+1,j] } + cut_right[j] - cut_left[i] (if i != j) i<=k<=j-1 = 0 (if i == j) = -無限大 (if i > j) 因此我們可以開始用 DP 填表格的方式, 填一個 n * n 的表格且填每一格所需的時間為 O(n) 故時間複雜度為 O(n^3) (註1) C[i,j] 當 i > j時, 表示這段木頭並不是atomic, 即可切割因此可以將C[i,j] 切割成 C[i,k], C[k+1,j] (註2)(i<=k<=j-1). 而將 C[i,j] 劃分成兩塊的 cost 為 cut_right[j]-cut_left[i] (註2) 為甚麼將 C[i,j] 劃分成的兩段木頭 L1 : i,i+1,...k 及 L2 : k+1,k+2...j 所切割的 cost (令為L1[i,k],L2[k+1,j]) 必定要是 C[i,k],C[k+1,j](最小成本)? 假設 C[i,j] 劃分出來的兩段 L1, L2 有一邊所切割的 cost 不為最小成本因為若其中有一段不是最小成本(設為L1[i,k], 因此 C[i,j] = L1[i,k] + C[k+1,j] + cut_right[j] - cut_left[i]), 則必定有一C'[i,j] = C[i,k] + C[k+1,j] + cut_right[j] - cut_left[i] < C[i,j] = L1[i,k] + C[k+1,j] + cut_right[j] - cut_left[i] 而我們剛剛又假設 C[i,j] 為最小成本, 矛盾 --><-- 故L1[i,k] = C[i,k], L2[k+1,j] = C[k+1,j] -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.243.192 ※ king19880326:轉錄至看板 Prob_Solve 04/27 08:52

推

Yshuan

04/27 09:30,

04/27 09:30

→

a127a127

04/27 09:54,

04/27 09:54

→

a127a127

04/27 09:55,

04/27 09:55