原文:
算法起步之动态规划
求切割方案，使得销售收益最大，假设切割是零成本。大家可以注意到n=4时不切割价格是9而切割成2个2英寸的钢条价格则变成了10；显然这种切割方案可以获得最大利润，但是如果数值比较大那我们改怎么计算呢，假设我们的钢条长度为g，我们可以将其分为2份，gi+gr；gi与gr的利润最大值加起来则是g的最大利润，我们使gi在1到10之间取值，显然gi的值我们可以先求出，而求gr的最大利润问题跟我们原问题又相同，很明显我们可以通过递归来解决这个问题。递归的方法：
动态规划其实是类似于分治算法，说白就是要解决这类问题需要依赖一个个的子问题解决。动态规划通常是用来求解最优化问题，设计一个动态规划的算法一般需要四步：
- 刻画一个最优解的结构特征。
- 递归定义最优解的值。
- 计算最优解的值采用自底向上的方法。
- 利用计算出的信息构造一个最优解。
我们先通过一个具体的例子来了解一下。
下图是某公司出售的一段长度为i英寸的共条的价格表：
| 长度i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 价格p | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
public void start(int l){
int[] p=null;
if(l>=10){
p=new int[l+1];
}else{
p=new int[11];
}
p[1]=1;
p[2]=5;
p[3]=8;
p[4]=9;
p[5]=10;
p[6]=17;
p[7]=17;
p[8]=20;
p[9]=24;
p[10]=30;
int result=cutrow(p, l);
System.out.println(result);
}
public int cutrow(int[] p,int n){
if (n==0) {
return 0;
}
int q=-1;
for (int i = 1; i <=n; i++) {
q=max(q, p[i]+cutrow(p,n-i));
}
return q;
}
public int max(int a,int b){
if (a>b) {
return a;
}else {
return b;
}
}
这种方法可以解决问题，但是当数值变大后会发现运行效率不高。原因在于已经求得的最大值我们没有直接用，而又进行了递归运算，这里有两种解决方案，1带备忘的自顶向下方法2自底向上方法。
带备忘的自顶向下方法：
public void start2(int l){
int[] p=null;
if(l>=10){
p=new int[l+1];
}else{
p=new int[11];
}
p[1]=1;
p[2]=5;
p[3]=8;
p[4]=9;
p[5]=10;
p[6]=17;
p[7]=17;
p[8]=20;
p[9]=24;
p[10]=30;
int result=memoizedcutrod(p, l);
System.out.println(result);
}
public int memoizedcutrod(int[] p,int n){
int[] r=new int[n+1];
return memoizedcutronaux(p, n, r);
}
public int memoizedcutronaux(int[]p,int n,int[]r){
if(r[n]>0){
return r[n];
}
if(n==0){
return 0;
}else {
int q=-1;
for (int i = 1; i <= n; i++) {
q=max(q, p[i]+memoizedcutronaux(p, n-i, r));
}
r[n]=q;
return q;
}
}
自底向上方法：
public void start1(int l){
int[] p=null;
if(l>=10){
p=new int[l+1];
}else{
p=new int[11];
}
p[1]=1;
p[2]=5;
p[3]=8;
p[4]=9;
p[5]=10;
p[6]=17;
p[7]=17;
p[8]=20;
p[9]=24;
p[10]=30;
int result=buttomupcutrow(p, l);
System.out.println(result);
}
public int buttomupcutrow(int[]p,int n){
for(int j=1;j<=n;j++){
int q=-1;
for (int i = 1; i <=j; i++) {
q=max(q,p[i]+p[j-i]);
}
p[j]=q;
}
return p[n];
}
可以看出自底向上的方法最为简单，这也是我们以后最为常用的一种方法。
友情提示：转载请注明出处【作者：idlear 博客：http://blog.csdn.net/idlear】
