動態規劃之鋼條切割問題

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 米的位置，我們均可以選擇切割或者不切割?，F在我們考慮將一段長度為 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. 小結

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