[問題] 請問有關鋸木問題寫成程式比較快的方法
看板C_and_CPP (C/C++)作者king19880326 (OK的啦～我都可以接受)時間16年前 (2009/04/27 08:51)推噓7(7推 0噓 9→)留言16則, 6人參與討論串1/1
題目敘述如下
有一個木頭, 長度是 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)
這樣的時間複雜度好像有點高 @@>, 請問有什麼方法可以把它的時間複雜度往下降嗎??
感謝感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.243.192
※ king19880326:轉錄至看板 Prob_Solve 04/27 08:52
推
04/27 09:30, , 1F
04/27 09:30, 1F
→
04/27 09:54, , 2F
04/27 09:54, 2F
→
04/27 09:55, , 3F
04/27 09:55, 3F
→
04/27 10:01, , 4F
04/27 10:01, 4F
推
04/27 12:05, , 5F
04/27 12:05, 5F
推
04/27 13:30, , 6F
04/27 13:30, 6F
→
04/27 13:48, , 7F
04/27 13:48, 7F
※ king19880326:轉錄至看板 Programming 04/27 13:52
→
04/27 17:35, , 8F
04/27 17:35, 8F
推
04/27 18:06, , 9F
04/27 18:06, 9F
→
04/27 18:06, , 10F
04/27 18:06, 10F
→
04/27 18:13, , 11F
04/27 18:13, 11F
推
04/27 19:14, , 12F
04/27 19:14, 12F
→
04/27 19:15, , 13F
04/27 19:15, 13F
推
04/27 19:31, , 14F
04/27 19:31, 14F
推
04/28 02:52, , 15F
04/28 02:52, 15F
→
04/28 04:57, , 16F
04/28 04:57, 16F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
