动态规划算法

  1 #include"stdafx.h"
  2 #include<iostream>
  3 using namespace std;
  4 /*
  5 动态规划算法:
  6 1.刻画一个最优解的结构特征
  7 2.递归地定义最优解的值
  8 3.计算最优解的值，通常采用自底向上的方法
  9 4.利用计算出的信息构造一个最优解.
 10 */
 11 /*普通递归法*/
 12 int CutRod(int *p ,int n)
 13 {
 14     if(n==0)
 15         return 0;
 16     int q=0;
 17     for(int i = 1;i<=n;++i)
 18     {
 19         q=max(q,p[i]+CutRod(p,n-i));
 20     }
 21     return q;
 22 }
 23 
 24 /*加入了备忘录机制*/
 25 int CutRodMemoized(int *p ,int *r,int n);
 26 int memory(int *p ,int n)
 27 {
 28     int *r = new int[n];
 29     for(int i =0 ;i!=n;i++)
 30     {
 31         r[i]=-1;
 32     }
 33     return CutRodMemoized(p,r,n);
 34 }
 35 int CutRodMemoized(int *p ,int *r,int n)
 36 {   
 37     if(r[n]>=0)
 38         return r[n];
 39     int q = -1;
 40     if(n==0)
 41         q = 0;
 42     else{
 43         q=-1;
 44         for(int i = 1;i<=n;++i)
 45             q=max(q,p[i]+CutRodMemoized(p,r,n-i));
 46     }
 47     r[n]=q;
 48     return q;
 49 }
 50 
 51 /*自底向上版本*/
 52 int BottomUp(int *p,int n)
 53 {
 54     int *r = new int[n];
 55     r[0]=0;
 56     for(int j = 1;j<=n;j++)
 57     {
 58         int q = -1;
 59         for(int i = 1;i<=j;i++){
 60          q = max(q,p[i] +r[j-i]);
 61         }
 62         r[j]=q;
 63     }
 64     return r[n];
 65 }
 66 
 67 /*自底向上版本扩展,记录切割点,也就是实现第四步,构造出最优解*/
 68 int BottomUpExtent(int *p,int n,int *r,int *s);
 69 void BottomExtent(int *p,int n)
 70 {
 71     int *r = new int[n];
 72     int *s = new int[n];
 73     cout<<"最大收益"<<BottomUpExtent(p,n,r,s)<<endl;
 74     cout<<"切割方式为:"<<endl;
 75     while(n>0){
 76         cout<<s[n]<<"  ";
 77         n = n-s[n];
 78     }
 79 }
 80 int BottomUpExtent(int *p,int n,int *r,int *s)
 81 {
 82     
 83     r[0]=0;
 84     s[0]=0;
 85     for(int j = 1;j<=n;j++)
 86     {
 87         int q = -1;
 88         for(int i = 1;i<=j;i++){
 89             if(q<p[i]+r[j-i])
 90             {
 91                  q = p[i] +r[j-i];
 92                  s[j] = i;
 93             }
 94         
 95          
 96         }
 97         r[j]=q;
 98     }
 99     return r[n];
100 }
101 
102 int _tmain(int argc, _TCHAR* argv[])
103 {
104     int q[11]={0,1,5,8,9,10,17,17,20,24,30};
105     cout<<CutRod(q,8)<<endl;
106     cout<<memory(q,8)<<endl;
107     cout<<BottomUp(q,8)<<endl;
108     BottomExtent(q,8);
109 }