问题描述
某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为英寸。已知价格表 $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})$
其他
在搜索过程中发现已有的文章：【基础算法】动态规划详解——钢条切割