2025年算法：动态规划-切木头问题（钢条切割问题）

大家好，我是讯享网，很高兴认识大家。

给自己留个纪念吧：一学期的算法课结课（2017年1月3日）期末考试结束，期末考试A了前三道，贴一道动态规划的题目吧。

考试题目上机的题目是这样的：

切原木问题：给定一根长度为 $N$ 米的原木；另有一个分段价格表，给出长度 $,$ 对应的价格 $P^{ L }$ 。要求你找出适当切割原木分段出售所能获得的最大收益 $R^{ N }$ 。例如，根据下面给出的价格表，若要出售一段8米长的原木，最优解是将其切割为2米和6米的两段，这样可以获得最大收益 $R^{ 8 } = P^{ 2 } + P^{ 6 } = 5 + 17 = 22 。$ 。而若要出售一段3米长的原木，最优解是根本不要切割，直接售出。

Length $L$	1	2	3	4	5	6	7	8	9	10
Price $P^{ L }$	1	5	8	9	10	17	17	20	23	28

输入原木头的长度；

输出最大价值；

例如输入8；输出22；

好，下面开始思考总结：采用填表自底向上的经典动态规划来做。

对于长度为n的钢条总共有
讯享网种不同的切割方案。设距离钢条左端i（i = 1,2,....n-1）英寸处为可切割点，那么我们对每个切割点都可以选择切或者不切，则总共有种方法。因此暴力枚举每一种可能是不行的。

动态规划（Dynamic Programming， DP）思想启发于分治算法的思想，也是将复杂问题化解若干子问题，先求解小问题，再根据小问题的解得到原问题的解。但是DP与分治算法不同的是，DP分解的若干子问题，往往是互相不独立的，这时如果用分治算法求解，那么会对重叠子问题重复进行求解，从而使得浪费大量的时间。那么如果我们保存已经计算过的子问题的解，这样当再次计算该子问题时，可以直接使用，这样可以节约大量的时间。

DP正是利用一个表记录所有已经求解过的子问题的答案，只要一个子问题被求解过，就将其答案保存起来，无论以后的计算是否会用到，这就是DP的基本思想。

设计动态规划的四个步骤：

1、刻画一个最优解的结构特征。

2、递归地定义最优解的值。

3、计算最优解的值，通常采用自底向上的方法。

4、利用计算出的信息构造一个最优解。

DP和分治的相似

都是通过组合子问题的解来求解原问题。

DP中的“programming”指的是一种表格法，而非coding。

DP和分治的不同

分治步骤：（例如归并排序）
- 将问题划分为互不相交的子问题
- 递归地求解子问题
- 组合子问题的解，求出原问题的解
对于DP：
- 应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）
  - 这种情况下分治会做很多不必要的工作，会反复求解哪些公共子问题。
  - 而DP对每个子子问题只求解一次，将其解保存在一个表格中，无需每次都重新计算，避免重复工作。

下面来写一下递推公式：

假设我们最优的第一刀直接切出一个距离左端为i(i = 1, ....n-1)的钢条，这一段整体收益最大，即不再对这一段继续切割。我们只对剩余长度为n-i的钢条，继续切割，求其收益最大的切割方案，这样问题只化为一个更小的子问题。

由此，我们可以知道长度为n的递推公式为：

贴个代码

#include <iostream> #include <cstring> using namespace std; //自底向上，两个循环，不用递归； int main() { int n; cin>>n; int price[11]={0,1,5,8,9,10,17,17,20,23,28}; int *r=new int [n+1]; for(int i = 0; i<= n; ++i) r[i] = 0; //初始化 for(int i = 1; i <= n; ++i)//规模长度为i { int q = INT_MIN; for(int j = 1; j <= i; ++j)//计算规模为i的最大收益 { if(q < (price[j] + r[i-j]))//因为i>i-j，所以当计算r[i]时，r[i-j]已经解决，可以直接用 q = (price[j] + r[i-j]); //迭代q； } r[i] = q; //找出i这个位置的最优解； } cout<<r[n]; //最后是n这个位置，就是n米长的木头的最大价值。 }

讯享网

2025年算法：动态规划-切木头问题（钢条切割问题）

DP和分治的相似

DP和分治的不同

相关推荐