钢铁切割(动态规划详解)

题目概要：
给定一段钢条，和不同长度的价格，问如何切割使得总价格最大。
ex ：

为了求解规模为 n 的原问题，我们先求解形式完全一样，但规模更小的子问题。 即当完成首次切割后，我们将两段钢条看成两个独立的钢条切割问题实例。 我们通过组合相关子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大者，构成原问题的最优解。

最优子结构：

问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。

动态规划的两种实现方法：

带备忘的自顶向下法（记忆化搜索）。
自底向上法（将子问题按规模排序，类似于递推）。

算法导论用子问题图上按照逆拓扑序求解问题，引出记忆化搜索。
重构解（输出方案）：转移的时候记录最优子结构的位置。

除了动态规划的方法还有递归求解的方法。

附上代码：
注意看注释

#include
#include
#includeusing namespace std;const int N=1e3+10;
int n;
int w[N];
int r[N];       //记录切割子值的最大价值
int dp[N];
int test1(int n)// 自顶向下递归
{int res=-1;if(n==0)return 0;for(int i=1; i<=n; i++){res=max(res,w[i]+test1(n-i));}return res;
}int test2(int n)// 自顶向下 记忆化 递归搜索
{memset(r,-1,sizeof r);int res=-1;if(r[n]!=-1)return r[n];  //之前算过的直接return，记忆的优化if(n==0)return r[n]=0;   //记得特殊情况判出for(int i=1; i<=n; i++){res=max(res,w[i]+test2(n-i));}return r[n]=res; //直接在return的时候记忆。
}int test3(int n)   //自底向上的动态规划
{memset(r,0,sizeof r);for(int i=1; i<=n; i++){int res=0;for(int j=1; j<=i; j++){res=max(res,w[j]+r[i-j]);}r[i]=res;}return r[n];
}int main()
{cin>>n;for(int i=1; i<=n; i++)cin>>w[i]; //不同长度的价值;//三种方法cout<<test1(n)<<endl;cout<<test2(n)<<endl;cout<<test3(n)<<endl;return 0;
}
/*
10
1 5 8 9 10 17 17 20 24 30
*/

1.自顶向下递归

递归的意义就是递归成子问题，子问题再分解成子问题的子问题，再利用递归回的值返回到原问题，但是递归的方式是化成小问题，但是小问题的数量和不记忆使得递归的时间较长，效率过低，而且是从上到下递归，没有记忆化，但是在数据范围较少时，可以使用，代码比较好想一些。

2.自顶向下 记忆化 递归搜索

故名思意，带了一个记忆化，但是递归的话还是比较慢，这算是对递归的一个优化。

3.自底向上动态规划

通过小状态来递推出大状态，并且记忆，使得整个过程较快，并且做到了有记忆。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！