动态规划之钢条切割问题

1. 前言

本节内容是动态规划算法系列之一：钢条切割问题，主要讲解了什么是钢条切割问题，如何利用动态规划算法解决钢条切割问题，给出了钢条切割问题的实现伪代码并进行分析，并用 Java 语言进行了伪代码实现，帮助大家通过钢条切割问题更好的理解动态规划算法思想的应用。

2. 什么是钢条切割问题？

我们来考虑现实生活中的一个实际应用场景，某个钢材公司购买长钢条，将其切割为短钢条出售，其中切割过程本身不考虑成本，公司管理层想知道最赚钱的钢材切割方案。假设我们知道该钢材公司出售一段长度为 i 米的钢条的价格为 p (i)，对应的价目表如下：

所以，钢材切割问题的定义如下：当我们给定一段长度为 n 米的钢条和对应的一个价格表（ p (i), i = 1,2,3,…n)，求一个钢条切割方案，使得最终的销售收益 r (n) 最大。（在这里，我们要求切割的钢条必须为整米长度）

接下来，就让我们看看如何利用动态规划算法求解钢条切割问题吧。

3. 动态规划算法求解钢条切割问题

在应用动态规划算法之前，我们先来看一下应该如何去表示一段长度为 n 米的钢材切割问题。首先，我们可以很清楚的知道一段长度为 n 米的钢条一共有 2^n-1 种切割方案，因为在钢条的第 1,2,3，…，n-1 米的位置，我们均可以选择切割或者不切割。对于一段长度为 n 米的钢条，假设我们将他切割为 k 段，每一长度段记为 i₁，i₂，…，i_k 米，我们可以将切割方案记为 n= i₁+i₂+…+i_k，对应的收益 r (n) = p (i₁) + p(i₂) +… + p(i_k)。接下来，我们按照上一节介绍的动态规范算法的求解步骤来求解钢条切割问题。

1. 步骤 1: 刻画一个钢条切割最优解的结构特征

根据之前描述的，在钢条的第 1,2,3，…，n-1 米的位置，我们均可以选择切割或者不切割。现在我们考虑将一段长度为 n 米钢材切割的最大收益 r (n) 用小一点的钢材收益表示，假设这个时候我们可以选择切割一次或者不切割，那对应着的 n 米的钢材会有 n 种处理方案，分别为：{p (n)，r (1)+r (n-1), r (2)+r (n-2),…,r (n-2)+r (2),r (n-1)+r (1)}，这里的 p (n) 表示没有切割，这样我们就可以将计算一段长度为 n 米的钢材的最优化切割方案转换为小一点长度的钢材的最优化切割方案。

在这里，我们可以注意到，为了求解规模为 n 的问题，我们先求解形式完全一样，单规模更小的问题。当完成首次切割之后，我们将两段钢材看出两个独立的钢条切割问题。我们通过组合两个相关子问题的最优解，并在所有可能的两段切割方案中选择组合收益最大者，构成原问题的最优解。我们称钢条切割问题满足最优子结构性质：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。

2. 步骤 2: 递归的定义钢条切割的最优解

当我们清楚一个钢条切割最优解的结构特征之后，现在开始递归的定义钢条切割的最优解，我们先看一下前面几种简单的钢条切割的最优解是什么样的：

r (1) = 1，钢条长度为 1 米的钢条最优切割方法就是自身，因为已经无法切割了

r (2) = 5，钢条长度为 2 米的钢条切割方案有两种， 1+1 或者 2，对应的价值分别为 2 或 5，所以 r (2)=5

r (3) = 8，钢条长度为 3 米的钢条切割方案有四种， 3,1+2,2+1，对应的价值分别为 8,6,6，所以 r (3)=8

对应步骤 1 中的钢条切割问题的最优解的结构特征，我们可以递归的定义钢条切割问题的最优解：

r(n) = max { p(n), r(1)+r(n-1), r(2)+r(n-2),…,r(n-2)+r(2), r(n-1)+r(1)}

除了上述的钢条最优切割问题的最优解的定义之外，钢条切割问题还可以以另外一种相似的但是更为简单的方法去求解：将钢条左边切割下长度为 i 米的一段，只对右边剩下的长度为 n-i 的一段进行继续切割（递归求解），对左边的一段则不再进行切割。
此时，问题可以分解为：将长度为 n 的钢条分解为左边开始一段以及剩余部分继续分解的结果。这样，我可以得到对于上面公式的一个简化版本：

r(n) = max { p(i) + r(n-i) } , 1<= i <= n

至此，我们已经完成了递归的定义钢条切割问题的最优解；接下来，我们开始计算最优解的值。

3. 步骤 3： 计算钢条切割最优解的值

考虑到对于长度为 n 的钢条切割的最优解由其子问题决定，我们可以先求解长度较小的钢条切割的最优解，然后用较小长度的最优解去逐步求解长度较大的钢条切割的最优解。相关伪代码定义如下：

 CutSteelRod(p,n):{
     r[0...n] be a new array[]
 	r[0]=0
 	for (int i=1; i<=n; i++){
         q = Integer.MIN_VALUE
         for (int j=1;j<=i;j++){
             q = max(q,p[j]+r[i-j])
         }
         r[i]=q
     }
 	return r[n]
 }

算法的第 2 行定义了一个新数组 r [0…n] 用来说存储子问题的最优解，第 3 行将 r [0] 初始化为 0，因为长度为 0 的钢条没有收益。第 4 行到第 10 行是两个 for 循序，外层的 for 循环分别求解长度为 i 的钢条切割的最优解，内部的 for 循环是每一次求解最优解的具体过程。

4. 步骤 4： 利用计算出的信息构造一个钢条切割问题的最优解

前面的算法 CutSteelRod 可以计算出钢条切割问题通过动态规划算法计算出来的最优解，但是并不会返回解本身（对应的一个长度列表，给出每段钢条的切割长度），如果我们需要得出具体的解，就需要对步骤 3 中的切割算法进行重构，具体伪代码如下：

 ExtendCutSteelRod(p,n){
     r[0...n],s[0...n] be new arrays[]
     r[0]=0
     for (int i=1; i<=n; i++){
         q = Integer.MIN_VALUE
         for (int j=1;j<=i;j++){
             if(q < p[j]+r[i-j]){
                 q = p[j]+r[i-j]
                 s[i] = j
             }
         }
         r[i]=q
     }
     return r and s
 }

ExtendCutSteelRod 算法与 CutSteelRod 算法很相似，只是在算法的第 2 行创建了数组 s，并在求解规模为 i 的子问题时将第一段钢条的最优切割长度 j 保存在 s [i] 中，详见算法中的第 9 行。

4.JAVA 代码实现

在说明求解钢条切割问题的整个过程之后，接下来，我们看看如何用 java 代码实现钢条切割问题的求解。

import java.util.Scanner;

public class SteelBarCutProblem {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[] p = {0,1,5,8,9,10,17,17,20,24,30};
        int[] r = new int[p.length];
        int[] s = new int[p.length];

        System.out.println("请输入1到"+ (p.length-1)+"之间任意一个自然数: ");
        int n = scanner.nextInt();

        r[0] = 0;
        for(int i =1; i<=n; i++){
            int q = Integer.MIN_VALUE;
            for (int j=1; j<=i; j++){
                if(q < (p[j] + r[i-j])){
                    q = p[j] + r[i-j];
                    s[i] = j;
                }
            }
            r[i] = q;
        }

        System.out.println("长度为"+ n +"米长的钢材最大切割收益为："+r[n]);
        System.out.println("对应的具体每一段的切割长度如下：");
        while (n>0){
            System.out.println(s[n]);
            n = n - s[n];
        }
    }

运行结果如下：

请输入1到10之间任意一个自然数: 
8
长度为8米长的钢材最大切割收益为：22
对应的具体每一段的切割长度如下：
2
6

运行结果中首先需要输入一个自然数表示要切割的钢条的长度，然后对应输出该长度钢条切割之后的最大化收益以及具体的切割方法。

代码中第 8 行至第 10 行分别初始化对应长度的钢材的价格表，对应长度钢条切割之后的最大化收益数组，对应长度钢条满足最大化收益时第一次切割的长度。代码的第 15 行至第 25 行主要来实现步骤 4 中的 ExtendCutSteelRod 算法，用来计算最大化的切割收益及保存解，代码的 27 行至 32 行主要是对求解结果的输出。并且代码中引用了 Scanner 类用来进行交换处理，可以在控制台输入一段需要切割的钢条长度，然后返回对应的切割结果。

5. 小结

本节主要学习了利用动态规划算法求解钢条切割问题，学习本节课程掌握钢条切割问题的算法流程，知道分动态规划算法是如何解决此类最优化问题，并且可以自己用代码实现钢条切割问题的求解。在学习完本节课程之后，我们通过钢条切割问题这一实例介绍了动态规划算法的实际应用，帮助大家可以更好的理解动态规划算法。