算法13---动态规划钢材裁剪

  1 #include <stdio.h>  2 #include <stdlib.h>  3   4   5   6   7 #define infinity  -1  //负无穷  8 #define len 100  9  10  11  12 int cut_rod(int p[],int n); 13 void print_menoized_cut_rod(int p[],int n); 14 int menoized_cut_rod_aux(int p[],int r[],int s[],int n); 15 void bottomup_cut_rod(int p[],int r[],int s[],int n); 16 void PrintCutRodSolution(int p[], int n);//自底向上法 17  18  19 //自顶向下递归实现 20  21 int cut_rod(int p[],int n) 22 { 23     int max=infinity; 24  25     if (n==0) 26     { 27         return 0; 28     } 29  30     //printf("ok,start!\n"); 31     int temp=0; 32     for (int i = 0; i < n; i++) 33     { 34         temp=p[i]+cut_rod(p,n-i); 35         if (temp>max) 36         { 37             max=temp; 38         } 39     } 40     return max; 41 } 42  43  44 /* 45 下面我们采取动态规划的方法来求主要有两种方法 46 第一种方法称为带备忘的自顶向下法。此方法按照递归方式编写过程， 47 但过程会保存每个子问题的解——用数组r[i]记录总长度为i的钢管的最大收益值。 48 当需要一个子问题的解时，过程首先检查是否已经保存过此解，如果是，直接返回保存的值， 49 否则递归计算这个子问题。 50  51   第二种方法称为自底向上法，这是动态规划的常用方法，这种方法需 52   要我们将子问题按照规模排序，按由小到大的顺序进行求解——在本题 53   中即按i从1到n的顺序求解。每个子问题只需求解一次，并及时把结果 54   记录下来，以便后面调用。 55  56 */ 57  58  59 //首先先实现备忘录方法。带备忘录的自顶向下方法 60  61  void print_menoized_cut_rod(int p[],int n) 62  { 63      int r[len]={0};//记录长度为i时的最大收益 64      int s[len]={0};//用来记录对应的切割方式 65      for (int i = 0; i < n; i++) 66      { 67          r[i]=infinity; 68      } 69      printf("the most expensive method is \n", menoized_cut_rod_aux(p,r,s,n)); 70      printf("the way to cut as follow!\n"); 71      while(n>0) 72      { 73          printf("%d\t",s[n]); 74          n-=s[n]; 75      } 76      printf("\n"); 77  } 78  79  80 int menoized_cut_rod_aux(int p[],int r[],int s[],int n) 81 { 82     int max; 83     if (r[n]>=0) 84     { 85         return r[n]; 86     } 87     if (n==0) 88     { 89         max=0; 90     } 91     else 92     { 93         max=infinity; 94         for (int i = 0; i < n; i++) 95         { 96             int temp=p[i]+menoized_cut_rod_aux(p,r,s,n-i); 97             if (temp>max) 98             { 99                 max=temp;100                 s[n]=i;101             }102         }103     }104     return max;105 }106 107 //由底到顶的方法108 void PrintCutRodSolution(int p[], int n)109 {110     int r[len]={0};111     int s[len]={0};112     bottomup_cut_rod(p,r,s,n);113     printf("the most value cut method solve by bottom to up:%d\n",r[n] );114     printf("the cut method:\n");115     while(n>0)116     {117         printf("%d\t",s[n]);118         n-=s[n];119     }120     printf("\n");121 }122 123 124 void bottomup_cut_rod(int p[],int r[],int s[],int n)125 {126     int max;127     for (int i = 0; i <= n; i++)128     {129         max=infinity;130         for (int j = 1; j <= n;j++)131         {132             if (max>p[j]+r[i-j])133             {134                 max=p[j]+r[i-j];135                 s[i]=j;136             }137         }138         r[i]=max;139     }140 }141 142 143 144 int main()145 {146     int p[10]={1,5,8,9,10,17,17,20,24,30};147     int n=4;148     // 先递归得出结果149     int ans=cut_rod(p,n);150 151     printf("the most benifit is %d\n", ans);152     // 按照从底到顶的方法153     PrintCutRodSolution(p,n);154     printf("\n");155     //按照从顶到底，备忘录法156     print_menoized_cut_rod(p,n);157     return 0;158 }