钢条切割问题

动态规划通常用于解决最优化问题，在这类问题中，通过做出一组选择来达到最优解。在做出每个选择的同时，通常会生成与原问题形式相同的子问题。当多于一个选择子集都生成相同的子问题时，动态规划技术通常就会很有效，其关键技术就是对每个这样的子问题都保存其解，当其重复出现时即可避免重复求解。

一 钢条切割问题

Serling公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。钢条的长度均为整英寸。图15-1给出了一个价格表的样例。

钢条切割问题是这样的：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n)，求切割钢条方案，使得销售收益rn最大。注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。

二 解决方案

1 暴力递归（多叉树遍历）

时间复杂度：2^n

伪代码如下：

代码实现：

//方法一：暴力递归 2^n复杂度（多叉树遍历）
int cutrod(vector<int> & p,int n ){
    
    if(n == 0) return 0;
    int q = INT_MIN;
    for(int i = 1; i <= n; ++i){
//        int temp = p[i] + cutrod(p, n - i);
//        if(temp > q)
//            q = temp;
        q = max(q,p[i]+cutrod(p, n-i));
    }
    return q;
}

递归过程：

2 带备忘录的递归（自顶向下）

伪代码：

代码实现：

//方法2:带备忘录的递归（自顶向下）
int mem_cutrodHelper(vector<int> & p,int n,vector<int> & r){
    //首先检查所需的值是否存在
    if(r[n] > 0) return r[n];
    
    int q = INT_MIN;//q是盈利
    if(n == 0)
        q = 0;
    else{
        for(int i = 1 ; i <= n; ++i){
            q = max(q,p[i]+mem_cutrodHelper(p, n-i, r));
        }
    }
    r[n] = q;
    return q;
}
int mem_cutrod(vector<int>& p,int n){
    vector<int> r(n + 1,-1);
    return mem_cutrodHelper(p,n,r);
}

3 动态规划（自底向上）

伪代码：

代码实现：

//方法3-1:动态规划
int dp_cutrod(vector<int> & p,int n ){
    vector<int> dp(n+1);//dp[i]表示 i长的钢条，最大收益是多少。
    dp[0] = 0; //动态规划的第一步，初始化非常重要。最小的最优子结构一定正确。
    for(int i = 1; i <= n; ++i){
        int q = -1;
        for(int j = 1 ; j <= i;++j){
            q = max(q,p[j] + dp[i -j]);//状态转移方程。
        }
        dp[i] = q;
    }
    return dp[n];
}
//方法3-2:直接套用状态方程   dp[i] = max(dp[i],p[j] + dp[i -j])
int dp_cutrod2(vector<int> & p,int n ){
    vector<int> dp(n+1);//dp[i]表示 i长的钢条，最大收益是多少。
    dp[0] = 0; //动态规划的第一步，初始化非常重要。最小的最优子结构一定要正确。
    for(int i = 1; i <= n; ++i){
        for(int j = 1 ; j <= i;++j){
            dp[i] = max(dp[i],p[j] + dp[i -j]);//状态转移方程。
        }
    }
    return dp[n];
}

4 代码重构

伪代码：

代码实现：

//方法4 重构的代码：可以输出最优切割方案，并打印出dp数组。
int print_dp_cutrod(vector<int> & p,int n){
    vector<int> cutpos(n+1);//存储长度为i的钢条 最优切割位置
    vector<int> dp(n + 1);
    dp[0] = 0;
    for(int i = 1; i <= n; ++i){
        int q = -1;
        for(int j = 1; j <= i; j++){
            //要想能够对切割方案进行输出，就不能一股脑的简化代码，
            //要对代码进行细粒度控制。把控好每一步。
            int temp = p[j] + dp[i - j];
            if(q < temp){
                q = temp;
                cutpos[i] = j;
            }
        }
        dp[i] = q;
    }
    std::cout<<"钢条的切割位置：";
    for(int i = 0 ; i < n+1;i++){
        std::cout<< cutpos[i] << " ";
    }
    std::cout<<endl;
    std::cout<<"dp数组：";
    for(int i = 0 ; i < dp.size();i++){
        cout<<dp[i]<<" ";
    }
    std::cout<<endl;
    cout << "最优切割策略: ";
    for(int i = cutpos.size()-1; i > 0; i -= cutpos[i]){
        cout<<cutpos[i]<<" ";
    }
    cout<<endl;
    return dp[n];
}

正确输出：