钢条切割问题-动态规划-c语言实现

问题：某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。已知价格表p，其中pi（i＝1，2，...，m）表示长度为i英寸的钢条的价格。现要求解使销售收益最大的切割方案。
求解此切割方案的算法基本思想如下：
假设长钢条的长度为n英寸，最佳切割方案的最左边切割段长度为i英寸，则继续求解剩余长度为n－i 英寸钢条的最佳切割方案。考虑所有可能的i，得到的最大收益rn对应的切割方案即为最佳切割方案。rn的递归定义如下：
rn =max1≤ i ≤n（pi rn-i）
对此递归式，给出自顶向下和自底向上两种实现方式。

（1）自顶向下方法：

把大问题划分为小问题，递归解决

以n=4为例子，画出他的树形图

由上面的树图可以看出自顶向下方法的时间复杂度为O(2的n次方)，就算有辅助数组也阻止不了他的计算量呈指数增长。

（1）自底向上方法：

自底向上方法是把自顶向下方法的反过来，自底向上方法直接从小问题求起，逐步求出大问题

自底向上方法的时间复杂度为O(n的平方)

c代码

1.  
   #include <stdio.h>
2.  
    
3.  
   #define maxp 100
4.  
   //动态规划
5.  
   int pd[maxp] = {0}; //pd[i] = max(pd(n-i) profit[j]) 保存各个子问题钢条的最大价值
6.  
    
7.  
   /**
8.  
   * @brief 自顶向下方法，获得钢条切割的最大价值
9.  
   *
10.  
    * @param n 钢条长度
11.  
    * @param pro 钢条价格表
12.  
    * @return int 钢条切割的最大价值
13.  
    */
14.  
    int Top_Down_Max_Value(int n, int pro[]){ //自顶向下方法，获得钢条切割的最大价值
15.  
    int maxValue = 0;
16.  
    int temp = 0;
17.  
    if(pd[n] > 0) return pd[n]; //子问题的最大切割价值已存在，直接查表，增加效率
18.  
    for (int i = 1; i <= n; i ) //有n种切割方法
19.  
    {
20.  
    temp = Top_Down_Max_Value(n-i, pro) pro[i]; //各种切割的总价格
21.  
    maxValue = (temp > maxValue) ? temp : maxValue; //比较各种切割的总价格，选出最大
22.  
    }
23.  
    return pd[n] = maxValue;
24.  
    }
25.  
     
26.  
    int Bottom_Up_Max_Value(int n, int pro[]){
27.  
    int temp = 0;
28.  
    for (int j = 1; j <= n; j ){ //从底向上，先求n=1钢条长度的最大价格，在通过n=1钢条长度的最大价格可以求出n=2钢条长度的最大价格，以此类推直到求到n
29.  
    temp = 0;
30.  
    for (int i = 1; i <= j; i ){ //选出n=j钢条长度的最大价格赋值给pd[j]
31.  
    temp = (pro[i] pd[j-i] > temp) ? pro[i] pd[j-i] : temp;
32.  
    }
33.  
    pd[j] = temp;
34.  
    }
35.  
    return pd[n];
36.  
    }
37.  
     
38.  
    int main(void){
39.  
    int n = 10;
40.  
    int pro[11] = {0,1,5,8,40,13,17,18,22,25,30};
41.  
    // printf("自顶向下方法%d长度的钢条的切割的最大价格为：%d\n", n, Top_Down_Max_Value(n, pro));
42.  
    printf("自底向上%d长度的钢条的切割的最大价格为：%d\n", n, Bottom_Up_Max_Value(n, pro));
43.  
    for (int i = 0; i < 11; i )
44.  
    {
45.  
    printf("%d ", pd[i]);
46.  
    }
47.  
     
48.  
    return 0;
49.  
    }

结果：

这篇好文章是转载于：学新通技术网