尽管排序算法还有很多没有说，但因为这篇⽂章是已经现成有的，就先上这个，回头再把排序补⼀下。
好的开始~BigMoyan有⼀个好基友叫zou先⽣，zou先⽣除了是BigMoyan在学校的社团⽼⼤外，还是⼀家专门为夜总会提供钢管的公司的区域经理。最近，zou经理发现这样⼀个事情，夜总会需要各种长度的钢管⽤作各种⽤途，然⽽每种长度的钢管的价格却不⼀样，总⽽⾔之如下表。
从前，zou经理总是傻乎乎的把总公司发来的10m长钢管以25块的价格卖出去，但是某天他跟学校的打菜阿姨聊起⼈⽣和事业的时候，打菜阿姨却来了⼀句：
“明明每根钢管能卖27块钱，你只卖25，学过C++吗？”
这深深伤害了zou经理的⼼灵，于是他向室友Jie求救。
以下是BigMoyan转述Jie的分析：
⾸先我们正式的表达⼀下这个问题，有⼀段长度为i的钢管，整段出售的价格为Pi，求适当的切割钢条⽅案使得获利最⼤。为了便于zou 理解问题，jie先⽤⼀个例⼦做了⼀下简单说明。 抱毯
⽐如你现在有⼀段长为4m的钢管，如果整段卖的话，卖9块。然⽽你也可以切成两段2m的钢管分别卖，这样⼀共可以卖5*2=10块，所以并不是整段卖就⼀定获益最⼤的。假设对于长为i的钢管，获益最⼤的售价为Ri，我们试着穷举⼀下。
长为1的钢管，i=1，只能整段出售，R1=1
长为2的钢管，i=2，很容易发现整段出售获益最⾼，R2=2
…
长为4的钢管，i=4，上⾯分析了应该切成两段，R4=10=5+5
长为5的钢管，整段出售是10块，分成1+4，因为R4=10，所以可以卖11块，分成2+3，则可卖13块，因此R5=2+3=13
…
由于jie看了BigMoyan关于快速排序的介绍，受到分治策略的影响，于是jie刚开始⾃然⽽然的认为这是⼀个可以递归解决的问题，对于长为i的钢管，其最⼤获益为：
Ri= max{Pn, R1+Rn-1,R2+Rn-2,…Ri-1+R1}
这个意思是说，为了求Ri，我们可以把钢管分为和为i的两段，⽽这两段各⾃⼜是⼀个求⼤获益的问题，正如BigMoyan曾经说过的那样，想要理解递归，⾸先，你要理解递归。然后在各种分法中出最⼤的那个，⾃然就是结果。注意上式中第⼀个参数Pn为整段出售的价格。
Jie把思路告诉了BigMoyan，BigMoyan很快为zou写了这样⼀段程序（没错我就是这样⼀个仗义的⼈），⽤C++写⼤概是下⾯这个样⼦（BigMoyan⽤的最多的依然是Python，可惜Python没有做尾递归优化，只能暂时⽤⼀把C++了）：
#include<iostream>
using namespace std;
int Max(int i, int j){
return i>j?i:j;
}
int cut_rod(int p[],int n){
if(n==0)
return0;
int f=0;
int q=-1;除水器
for(int i=1;i!=n;i++){
f=Max(p[n-1],cut_rod(p,i)+cut_rod(p,n-i));
q=Max(q,f);
}
return q;
}
int main(){
int p[10]={1, 5, 8, 9, 10, 17, 17, 20, 24, 25};
固体氧
int f=cut_rod(p,10);
cout<<f;
⽼规矩，碰到代码不要慌，拿个实例稍微分析⼀下，例如求长为5的钢管的最⼤收益。调⽤函数cut_rod(p,5) 进去以后， if测试失败，进⼊for循环
i=1:
f=Max(p[4],cut_rod(p,1)+cut_rod(p,4));
出了p[4]和cut_rod(p,1)+cut_rod(p,4)的⼤者，前者为5m钢管整段出售的价格（下标从0开始所以是5-1=4），后者将5m分为1m和
4m，将两段的最⼤收益加起来作为进⾏1+4分割的最⼤收益。
q=Max(q,f);
第⼀趟的时候q=-1，所以此时q=f保存1+4分割时的最⼤收益。
i=2:
f=Max(p[4],cut_rod(p,1)+cut_rod(p,4));
如上，此次的是整段出售和2+3分割的最⼤收益之间的⼤者。
q=Max(q,f);
q在上次保存了f，这次将新f和上⼀次的值(q)⽐较，拿出最⼤的作为最⼤收益
后⾯以此类推
然⽽在测试代码的时候BigMoyan发现，这代码执⾏效率太他喵的低了！n⽐较⼤的时候，基本上n增加1，代码运⾏时间就要加两倍，我要敢测试⼀个500m长的钢管的最⼤收益（假设数据都有），估计zou经理都要毕业了。
稍加分析发现，执⾏效率低的原因在于⼦问题⼀直在重复计算！计算10m钢管收益的时候要把1~9m的收益全算⼀次，⽽为了计算9m钢管的收益，我⼜要把1~8m的都算⼀次。
⼼！好！累！
此时聪明的jie也已经察觉到了问题所在，这个问题看起来是递归，其实却与递归略有不同。递归的⼦问题互相不相交，⽽这个东西的⼦问题是相交的，相同的⼦问题被⼀遍⼀遍的计算，才导致了效率的低下。
Jie略⼀思忖，计上⼼来，既然⼦问题被⼀遍遍的计算，我们何不以空间换时间，把已经被计算好的⼦问题的结果保存起来，当需要的时候⾸先查询，如果这个问题已经算好了，直接拿来⽤就是，若没算好再进⾏计算。
BigMoyan拍案叫绝，再次改写了代码，于是就有了下⾯这段C++ code：
nt cut_rod(int p[],int n){
int *r=new int[n];
for(int i=0;i!=n;i++)
r[i]=-1;
return cut_rod_memo(p,n,r);
}
调⽤函数名保持⼀致⽅便理解，⾸先建⽴⼀个备忘录r，r⽤来保存已经被计算好的⼦问题的答案。将它初始化为-1。我们还是以计算5m 钢管为例，那么r被初始化为[-1,-1,-1,-1,-1].
接着调⽤cut_rod_memo来计算最⼤收益，那么cut_rod_memo是什么呢？
nt cut_rod_memo(int p[], int n, int r[]){
if(r[n-1]>=0)
return r[n-1];
if(n==0)
int q=0;
else{
int f=0;
int q=-1;
for(int i=1;i!=n;i++){
受机
f=Max(p[n-1],cut_rod_memo(p,i,r)+cut_rod_memo(p,n-i,r));
q=Max(q,f);
}
r[n-1]=q;
好的，不要头⼤，BigMoyan慢慢分析。
进⼊cut_rod_memo后，⾸先查询5m的结果是不是已经算好了，答案是当然没有，r[4]=-1。于是进⼊else语句，这⾥的语句跟之前递归的版本⼀模⼀样，区别只在于递归调⽤的是cut_rod_memo，因为该函数⾥第⼀个语句就是判断⼦问题答案有没有做好，所以避免了多次计算相同的⼦问题，下⾯展⽰这⼀过程。
i=1:
由之前的⽆脑递归的版本可知，for循环解决了i=1时的最⼤收益，在for循环完成后，将其保存在r[0]中，此时r[0]=1
i=2:
在递归调⽤cut_rod_memo(p,1,r)时，因为已经算好r[0]=1，故cut_rod_memo的第⼀个if判断成功，返回r[0]，此时的返回值由已经计算过的结果直接拿出，没有重新计算。
其他情况同理。
BigMoyan与jie两⼈相对⽽笑，笑容中充满着对对⽅的赞赏。他们⼀起来到zou经理折戟的银桦⾷堂，与打菜阿姨如此这般⼀讲，本指望收到阿姨赞美的眼光，没想到阿姨把勺⼦⾥的菜抖掉⼀些，淡然说道：
“唔？这不就是动态规划吗，什么新鲜东西，值得来浪，刷卡！”
Ps.动态规划问题当然不⽌这⼀类，但其基本思想是⼀致的，就是不要重复解决已经解决过的问题，感兴趣的同学可以百度⼀下动态规划
PPS：下⾯是全部C++代码
1 #include<iostream>
2using namespace std;
3
4int Max(int i, int j){
氧氟沙星甘露醇5return i>j?i:j;
6 }
7
8int cut_rod_memo(int p[], int n, int r[]){
9if(r[n-1]>=0)
10return r[n-1];
11if(n==0)
12int q=0;
13else{
14int f=0;
15int q=-1;
16for(int i=1;i!=n;i++){
17 f=Max(p[n-1],cut_rod_memo(p,i,r)+cut_rod_memo(p,n-i,r));
18 q=Max(q,f);
19 }
20 r[n-1]=q;
21return q;
22 }
23 }
24
25int cut_rod(int p[],int n){
26int *r=new int[n];
27for(int i=0;i!=n;i++)
28 r[i]=-1;
29return cut_rod_memo(p,n,r);
30 }
31
32int main(){
33int p[10]={1, 5, 8, 9, 10, 17, 17, 20, 24, 25};
34int f=cut_rod(p,10);
35 cout<<f;
36return1;
缘114
37 }
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议