作者king19880326 (OK的啦～我都可以接受)
看板Programming
標題[問題] 請問有關鋸木問題寫成程式比較快的方法
時間Mon Apr 27 13:52:08 2009
※ [本文轉錄自 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)
這樣的時間複雜度好像有點高 @@>, 請問有什麼方法可以把它的時間複雜度往下降嗎??
感謝感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.243.192
※ king19880326:轉錄至看板 Prob_Solve 04/27 08:52
1F：推 Yshuan:我直覺的看 每刀都要切在中間會是cost最小 有錯嗎 @@~~! 04/27 09:30
2F：→ a127a127:給樓上 1 2 3 4 5 6 100000 04/27 09:54
3F：→ a127a127:試著把填一格的時間變成均攤的O(1) 04/27 09:55
4F：→ a127a127:一個簡單的觀察是：P(i,j) i固定,j越大時 切的點的位置.. 04/27 10:01
5F：推 evernever:我也是覺得切中間 (1+100000)/2..最接近 6...先切6 04/27 12:05
6F：推 littleshan:長度10，切割點 4, 5, 6 04/27 13:30
7F：→ king19880326:可以麻煩a127a127說得清楚些嗎@@?? 04/27 13:48
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.243.43
8F：推 bobju:就這個例子來看, 我想了解的是: 可允許的切 59.104.186.105 04/27 14:57
9F：→ bobju:法有幾種? 除了(3,4,8),(8,4,3)以外, 可不可 59.104.186.105 04/27 14:58
10F：→ bobju:以有其它的排列情形? 總共應有6種才對. 而最 59.104.186.105 04/27 14:58
11F：→ bobju:小成本即是這6種切法當中成本最小的那種. 59.104.186.105 04/27 14:59
12F：→ king19880326:恩 是考慮所有組合 140.112.243.43 04/27 17:37
13F：推 bobju:這個問題恐怕要跑遞迴,把所有排列情形都跑遍 59.104.186.105 04/27 18:56
14F：→ bobju:,再找出最小成本路徑. 59.104.186.105 04/27 18:57
15F：→ bobju:方法我有,只是時間複雜度不知如何估算. 59.104.186.105 04/27 18:57
16F：→ bobju:以n*n格為例,並非每一格都必需透過計算才能 59.104.186.105 04/27 19:04
17F：→ bobju:得值,其中應該有些格的值可以參考自其它格的 59.104.186.105 04/27 19:04
18F：→ bobju:值才對. 59.104.186.105 04/27 19:05
19F：推 operationcow:如果是跑所有組合那就是n!層了140.112.243.192 04/27 20:53
20F：→ operationcow:指數時間@_@140.112.243.192 04/27 20:53
21F：推 bobju:不見得,因為做動態規劃,在traversal的過程當 59.104.186.105 04/28 01:33
22F：→ bobju:中,可以蒐集到某些讓後面再跑到時會用得著的 59.104.186.105 04/28 01:33
23F：→ bobju:資訊,等於可以簡化某些路徑,所以未必是n!,可 59.104.186.105 04/28 01:34
24F：→ bobju:以再down一些時間成本. 59.104.186.105 04/28 01:34
25F：推 yoco315:O(nnn)?這題不是很直覺?還是我想的太簡單?118.160.108.151 04/28 13:16
26F：推 bobju:如果是O(n^3)那還好,因為我想了想,感覺不太 59.104.191.26 04/28 15:27
27F：→ bobju:像是O(n^3). 即使以n*n個表格的模型來思考, 59.104.191.26 04/28 15:27
28F：→ bobju:似乎也不能證明填上每一格的平均時間是O(n). 59.104.191.26 04/28 15:28
29F：→ bobju:因為每一刀切在某一點上的成本是隨著之前的 59.104.191.26 04/28 15:33
30F：→ bobju:截點序列的不同而變,而非一個定值. 59.104.191.26 04/28 15:33
31F：→ bobju:若是O(n^3), 則是多項式時間, 跟老闆交差他 59.104.191.26 04/28 15:40
32F：→ bobju:應該要偷笑了. XD 59.104.191.26 04/28 15:40