问题描述
给定长度为 $n$ 的一段钢条，以及一个价格表 $p$。这个价格表中标明了长度为 $l$ 的价格，其中 $l$ 为整数，取值范围为 $[0,n]$。
求一组切割方案，使得钢条的价格尽可能高。
问题分析
令 $r[n]$ 为长度为 $n$ 英寸的钢条的最大收益，则状态转移方程为
$$ \begin{align*} r[n] = \max_{1 \leqslant i \leqslant n}{p[i] + r[n-i]} \end{align*} $$算法代码
void rodCutting(const vector<int> &p) {
// 初始化
const int length = p.size();
vector<int> r(length + 1, 0); // r[i]表示切割长度为i的钢条可得最大总收益
vector<int> rec(length + 1, 0); // rec[i]记录长度为i的钢条的最优切割方案
// 动态规划
for (int j = 1; j <= length; ++j) {
r[j] = p[j];
rec[j] = j;
for (int i = 1; i <= j - 1; ++i) {
if (p[i] + r[j - i] > r[j]) {
r[j] = p[i] + r[j - i];
rec[j] = i;
}
}
}
// 输出结果
int n = length;
cout << "最优价格：" << r[n] << endl;
cout << "切割方式：" << endl;
while (n > 0) {
cout << rec[n] << ' ';
n = n - rec[n];
}
}
算法分析
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n)$