動態(tài)規(guī)劃之鋼條切割問題

1. 前言

本節(jié)內(nèi)容是動態(tài)規(guī)劃算法系列之一：鋼條切割問題，主要講解了什么是鋼條切割問題，如何利用動態(tài)規(guī)劃算法解決鋼條切割問題，給出了鋼條切割問題的實現(xiàn)偽代碼并進行分析，并用 Java 語言進行了偽代碼實現(xiàn)，幫助大家通過鋼條切割問題更好的理解動態(tài)規(guī)劃算法思想的應(yīng)用。

2. 什么是鋼條切割問題？

我們來考慮現(xiàn)實生活中的一個實際應(yīng)用場景，某個鋼材公司購買長鋼條，將其切割為短鋼條出售，其中切割過程本身不考慮成本，公司管理層想知道最賺錢的鋼材切割方案。假設(shè)我們知道該鋼材公司出售一段長度為 i 米的鋼條的價格為 p (i)，對應(yīng)的價目表如下：

所以，鋼材切割問題的定義如下：當我們給定一段長度為 n 米的鋼條和對應(yīng)的一個價格表（ p (i), i = 1,2,3,…n)，求一個鋼條切割方案，使得最終的銷售收益 r (n) 最大。（在這里，我們要求切割的鋼條必須為整米長度）

接下來，就讓我們看看如何利用動態(tài)規(guī)劃算法求解鋼條切割問題吧。

3. 動態(tài)規(guī)劃算法求解鋼條切割問題

在應(yīng)用動態(tài)規(guī)劃算法之前，我們先來看一下應(yīng)該如何去表示一段長度為 n 米的鋼材切割問題。首先，我們可以很清楚的知道一段長度為 n 米的鋼條一共有 2^n-1 種切割方案，因為在鋼條的第 1,2,3，…，n-1 米的位置，我們均可以選擇切割或者不切割。對于一段長度為 n 米的鋼條，假設(shè)我們將他切割為 k 段，每一長度段記為 i₁，i₂，…，i_k 米，我們可以將切割方案記為 n= i₁+i₂+…+i_k，對應(yīng)的收益 r (n) = p (i₁) + p(i₂) +… + p(i_k)。接下來，我們按照上一節(jié)介紹的動態(tài)規(guī)范算法的求解步驟來求解鋼條切割問題。

1. 步驟 1: 刻畫一個鋼條切割最優(yōu)解的結(jié)構(gòu)特征

根據(jù)之前描述的，在鋼條的第 1,2,3，…，n-1 米的位置，我們均可以選擇切割或者不切割?，F(xiàn)在我們考慮將一段長度為 n 米鋼材切割的最大收益 r (n) 用小一點的鋼材收益表示，假設(shè)這個時候我們可以選擇切割一次或者不切割，那對應(yīng)著的 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 米的鋼材的最優(yōu)化切割方案轉(zhuǎn)換為小一點長度的鋼材的最優(yōu)化切割方案。

在這里，我們可以注意到，為了求解規(guī)模為 n 的問題，我們先求解形式完全一樣，單規(guī)模更小的問題。當完成首次切割之后，我們將兩段鋼材看出兩個獨立的鋼條切割問題。我們通過組合兩個相關(guān)子問題的最優(yōu)解，并在所有可能的兩段切割方案中選擇組合收益最大者，構(gòu)成原問題的最優(yōu)解。我們稱鋼條切割問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)：問題的最優(yōu)解由相關(guān)子問題的最優(yōu)解組合而成，而這些子問題可以獨立求解。

2. 步驟 2: 遞歸的定義鋼條切割的最優(yōu)解

當我們清楚一個鋼條切割最優(yōu)解的結(jié)構(gòu)特征之后，現(xiàn)在開始遞歸的定義鋼條切割的最優(yōu)解，我們先看一下前面幾種簡單的鋼條切割的最優(yōu)解是什么樣的：

r (1) = 1，鋼條長度為 1 米的鋼條最優(yōu)切割方法就是自身，因為已經(jīng)無法切割了

r (2) = 5，鋼條長度為 2 米的鋼條切割方案有兩種， 1+1 或者 2，對應(yīng)的價值分別為 2 或 5，所以 r (2)=5

r (3) = 8，鋼條長度為 3 米的鋼條切割方案有四種， 3,1+2,2+1，對應(yīng)的價值分別為 8,6,6，所以 r (3)=8

對應(yīng)步驟 1 中的鋼條切割問題的最優(yōu)解的結(jié)構(gòu)特征，我們可以遞歸的定義鋼條切割問題的最優(yōu)解：

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)}

除了上述的鋼條最優(yōu)切割問題的最優(yōu)解的定義之外，鋼條切割問題還可以以另外一種相似的但是更為簡單的方法去求解：將鋼條左邊切割下長度為 i 米的一段，只對右邊剩下的長度為 n-i 的一段進行繼續(xù)切割（遞歸求解），對左邊的一段則不再進行切割。
此時，問題可以分解為：將長度為 n 的鋼條分解為左邊開始一段以及剩余部分繼續(xù)分解的結(jié)果。這樣，我可以得到對于上面公式的一個簡化版本：

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

至此，我們已經(jīng)完成了遞歸的定義鋼條切割問題的最優(yōu)解；接下來，我們開始計算最優(yōu)解的值。

3. 步驟 3： 計算鋼條切割最優(yōu)解的值

考慮到對于長度為 n 的鋼條切割的最優(yōu)解由其子問題決定，我們可以先求解長度較小的鋼條切割的最優(yōu)解，然后用較小長度的最優(yōu)解去逐步求解長度較大的鋼條切割的最優(yōu)解。相關(guā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 行定義了一個新數(shù)組 r [0…n] 用來說存儲子問題的最優(yōu)解，第 3 行將 r [0] 初始化為 0，因為長度為 0 的鋼條沒有收益。第 4 行到第 10 行是兩個 for 循序，外層的 for 循環(huán)分別求解長度為 i 的鋼條切割的最優(yōu)解，內(nèi)部的 for 循環(huán)是每一次求解最優(yōu)解的具體過程。

4. 步驟 4： 利用計算出的信息構(gòu)造一個鋼條切割問題的最優(yōu)解

前面的算法 CutSteelRod 可以計算出鋼條切割問題通過動態(tài)規(guī)劃算法計算出來的最優(yōu)解，但是并不會返回解本身（對應(yīng)的一個長度列表，給出每段鋼條的切割長度），如果我們需要得出具體的解，就需要對步驟 3 中的切割算法進行重構(gòu)，具體偽代碼如下：

 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 行創(chuàng)建了數(shù)組 s，并在求解規(guī)模為 i 的子問題時將第一段鋼條的最優(yōu)切割長度 j 保存在 s [i] 中，詳見算法中的第 9 行。

4.JAVA 代碼實現(xiàn)

在說明求解鋼條切割問題的整個過程之后，接下來，我們看看如何用 java 代碼實現(xiàn)鋼條切割問題的求解。

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)+"之間任意一個自然數(shù): ");
        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("對應(yīng)的具體每一段的切割長度如下：");
        while (n>0){
            System.out.println(s[n]);
            n = n - s[n];
        }
    }

運行結(jié)果如下：

請輸入1到10之間任意一個自然數(shù): 
8
長度為8米長的鋼材最大切割收益為：22
對應(yīng)的具體每一段的切割長度如下：
2
6

運行結(jié)果中首先需要輸入一個自然數(shù)表示要切割的鋼條的長度，然后對應(yīng)輸出該長度鋼條切割之后的最大化收益以及具體的切割方法。

代碼中第 8 行至第 10 行分別初始化對應(yīng)長度的鋼材的價格表，對應(yīng)長度鋼條切割之后的最大化收益數(shù)組，對應(yīng)長度鋼條滿足最大化收益時第一次切割的長度。代碼的第 15 行至第 25 行主要來實現(xiàn)步驟 4 中的 ExtendCutSteelRod 算法，用來計算最大化的切割收益及保存解，代碼的 27 行至 32 行主要是對求解結(jié)果的輸出。并且代碼中引用了 Scanner 類用來進行交換處理，可以在控制臺輸入一段需要切割的鋼條長度，然后返回對應(yīng)的切割結(jié)果。

5. 小結(jié)

本節(jié)主要學(xué)習(xí)了利用動態(tài)規(guī)劃算法求解鋼條切割問題，學(xué)習(xí)本節(jié)課程掌握鋼條切割問題的算法流程，知道分動態(tài)規(guī)劃算法是如何解決此類最優(yōu)化問題，并且可以自己用代碼實現(xiàn)鋼條切割問題的求解。在學(xué)習(xí)完本節(jié)課程之后，我們通過鋼條切割問題這一實例介紹了動態(tài)規(guī)劃算法的實際應(yīng)用，幫助大家可以更好的理解動態(tài)規(guī)劃算法。