题解：切割钢条

故宫 by Gigi

Guderian出品

说明

某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。已知价格表$ P$，其中中 $P_i（i＝1，2，…，m）$表示长度为$i$英寸的钢条的价格。现要求解使销售收益最大的切割方案 。

分析

算法设计策略：动态规划

假设长钢条的长度为$ n $英寸，最佳切割方案的最左边切割段长度为$ i $英寸，则继续求解剩余长度为$ n－i $英寸钢条的最佳切割方案。考虑所有可能的$ i$，得到的最大收益$ r_n$对应的切割方案即为最佳切割方案。$r_n$的递归定义如下：

$$r_n =\max_{1≤ i ≤n}(p_i +r_{n-i})$$

对此递归式，给出自顶向下和自底向上两种实现方式。

实现

（1）常量和变量说明

n：长钢条的长度

p[]：价格数组

（2）C语言程序

#include<stdio.h>
#define LEN 100

int Top_Down_Cut_Rod(int p[],int n){ /*自顶向下*/
    int r=0;
    int i;
    if(n==0){
        return 0;
    }
    for(i=1;i<=n;i++){
        int tmp=p[i]+Top_Down_Cut_Rod(p,n-i);
        r= (r>=tmp) ? r : tmp;
    }
    return r;
}

int Bottom_Up_Cut_Rod(int p[],int n){ /*自底向上*/
    int r[LEN]={0};
    int temp=0;
    int i,j;
    for(j=1;j<=n;j++){
        temp=0;
        for(i=1;i<=j;i++){
            temp=(temp>=p[i]+r[j-i]) ? temp : (p[i]+r[j-i]);
        }
        r[j]=(temp>=p[j]) ? temp : p[j];
    }
    return r[n];
}

int main()
{
    /*示例数据*/
    int p[11]={0,1,2,1,8,3,5,2,5,3,9};
    int a = Top_Down_Cut_Rod(p,10);
    int b = Bottom_Up_Cut_Rod(p,10);
    printf("%d %d\n",a,b);
    return 0;
}

（3）复杂度分析

• 自顶向下（爆搜）

  • 时间复杂度：$O(2^n)$
  • 空间复杂度：$O(1)$

• 自底向上

  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$