算法钢条切割问题 (动态规划分治)

问题描述

某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为英寸。已知价格表 $p$ ，其中 $p_{i}(i=1,2,\cdots,m)$ 表示长度为 $i$ 英寸的钢条的价格。现要求解使销售收益最大的切割方案

问题分析

假设长钢条的长度为 $n$ 英寸，最佳切割方案的最左边切割段长度为 $i$ 英寸，则继续求解剩余长度为 $m-1$ 英寸钢条的最佳切割方案。考虑所以可能的 $i$ ，得到的最大收益 $r_{n}$ 对应的切割方案即为最佳切割方案。$r_{n}$ 的递归定义如下 $$ r_{n}=max_{1\le i \le n}(p_{i}+r_{n-i}) $$

C 代码

对此问题有两种方案

(1) 分治 (自顶向下)

int Top_Down_Cut_Rod(int p[], int n){
    int r=0;	// 最大价值
    int i;
    
    if(n==0){
        retrun 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;
}

时间复杂度 $O(2^{n})$

(2) 动态规划 (自底向上)

int Bottom_Up_Cut_Rod(int p[], int n, int *s){
    // *s:子问题最优切割方法
    int r[n+1];	// 子问题最优价值
    r[0]=0;
    
    for(int j=1; j<=n; j++){
        int tmp=0;
        for(int i=1; i<=j; i++){
            if(p[i]+r[j-1] > tmp){
                tmp = p[i]+r[j-i];
                s[j]=i;
            }
        }
        r[i]=tmp;
    }
    
    return r[n];
}

时间复杂度 $O(n^{2})$

其他

在搜索过程中发现已有的文章：【基础算法】动态规划详解——钢条切割