钢条切割问题-动态规划-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代码

#include 

#define maxp 100
//动态规划
int pd[maxp] = {0};  //pd[i] = max(pd(n-i)+profit[j])  保存各个子问题钢条的最大价值


int Top_Down_Max_Value(int n, int pro[]){  //自顶向下方法，获得钢条切割的最大价值
    int maxValue = 0;
    int temp = 0;
    if(pd[n] > 0) return pd[n];  //子问题的最大切割价值已存在，直接查表，增加效率
    for (int i = 1; i <= n; i++)  //有n种切割方法
    {
        temp = Top_Down_Max_Value(n-i, pro) + pro[i];   //各种切割的总价格
        maxValue = (temp > maxValue) ? temp : maxValue;  //比较各种切割的总价格，选出最大
    }
    return pd[n] = maxValue;
}

int Bottom_Up_Max_Value(int n, int pro[]){
    int temp = 0;
    for (int j = 1; j <= n; j++){  //从底向上，先求n=1钢条长度的最大价格，在通过n=1钢条长度的最大价格可以求出n=2钢条长度的最大价格，以此类推直到求到n
        temp = 0;
        for (int i = 1; i <= j; i++){  //选出n=j钢条长度的最大价格赋值给pd[j]
            temp = (pro[i] + pd[j-i] > temp) ? pro[i] + pd[j-i] : temp;
        }
        pd[j] = temp;
    }
    return pd[n];
}

int main(void){
    int n = 10;
    int pro[11] = {0,1,5,8,40,13,17,18,22,25,30};
    // printf("自顶向下方法%d长度的钢条的切割的最大价格为：%dn", n, Top_Down_Max_Value(n, pro));
    printf("自底向上%d长度的钢条的切割的最大价格为：%dn", n, Bottom_Up_Max_Value(n, pro));
    for (int i = 0; i < 11; i++)
    {
        printf("%d ", pd[i]);
    }
    
    return 0;
}

结果：