📢 本文由 gemini-3-flash-preview 翻譯
問題描述
某公司購買長鋼條，將其切割後進行出售。切割鋼條的成本可以忽略不計，鋼條的長度為英吋。已知價格表 $p$ ，其中 $p_{i}(i=1,2,\cdots,m)$ 表示長度為 $i$ 英吋的鋼條的價格。現要求解使銷售收益最大的切割方案。
問題分析
假設長鋼條的長度為 $n$ 英吋，最佳切割方案的最左邊切割段長度為 $i$ 英吋，則繼續求解剩餘長度為 $m-1$ 英吋鋼條的最佳切割方案。考慮所有可能的 $i$ ，得到的最大收益 $r_{n}$ 對應的切割方案即為最佳切割方案。$r_{n}$ 的遞迴定義如下：
$$
r_{n}=max_{1\le i \le n}(p_{i}+r_{n-i})
$$C 程式碼
對此問題有兩種方案：
(1) 分治法 (自頂向下)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int Top_Down_Cut_Rod(int p[], int n){
int r=0; // 最大價值
int i;
if(n==0){
retrun 0;
}
for(i=1; i<=n; i++){
int tmp = p[i]+Top_Down_Cut_Rod(p, n-i);
r = (r>=tmp) ? r : tmp;
}
return r;
}
|
時間複雜度 $O(2^{n})$
(2) 動態規劃 (自底向上)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int Bottom_Up_Cut_Rod(int p[], int n, int *s){
// *s:子問題最佳切割方法
int r[n+1]; // 子問題最佳價值
r[0]=0;
for(int j=1; j<=n; j++){
int tmp=0;
for(int i=1; i<=j; i++){
if(p[i]+r[j-1] > tmp){
tmp = p[i]+r[j-i];
s[j]=i;
}
}
r[i]=tmp;
}
return r[n];
}
|
時間複雜度 $O(n^{2})$
其他
在搜尋過程中發現已有的文章：
【基礎算法】动态规划详解——钢条切割