JdreamZhang ·動(dòng)態(tài)規(guī)劃之鋼條切割問(wèn)題
1. 前言
本節(jié)內(nèi)容是動(dòng)態(tài)規(guī)劃算法系列之一：鋼條切割問(wèn)題，主要講解了什么是鋼條切割問(wèn)題，如何利用動(dòng)態(tài)規(guī)劃算法解決鋼條切割問(wèn)題，給出了鋼條切割問(wèn)題的實(shí)現(xiàn)偽代碼并進(jìn)行分析，并用 Java 語(yǔ)言進(jìn)行了偽代碼實(shí)現(xiàn)，幫助大家通過(guò)鋼條切割問(wèn)題更好的理解動(dòng)態(tài)規(guī)劃算法思想的應(yīng)用。
2. 什么是鋼條切割問(wèn)題？
我們來(lái)考慮現(xiàn)實(shí)生活中的一個(gè)實(shí)際應(yīng)用場(chǎng)景，某個(gè)鋼材公司購(gòu)買長(zhǎng)鋼條，將其切割為短鋼條出售，其中切割過(guò)程本身不考慮成本，公司管理層想知道最賺錢的鋼材切割方案。假設(shè)我們知道該鋼材公司出售一段長(zhǎng)度為 i 米的鋼條的價(jià)格為 p (i)，對(duì)應(yīng)的價(jià)目表如下：
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| p(i) | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
所以，鋼材切割問(wèn)題的定義如下：當(dāng)我們給定一段長(zhǎng)度為 n 米的鋼條和對(duì)應(yīng)的一個(gè)價(jià)格表（ p (i), i = 1,2,3,…n)，求一個(gè)鋼條切割方案，使得最終的銷售收益 r (n) 最大。（在這里，我們要求切割的鋼條必須為整米長(zhǎng)度）
接下來(lái)，就讓我們看看如何利用動(dòng)態(tài)規(guī)劃算法求解鋼條切割問(wèn)題吧。
3. 動(dòng)態(tài)規(guī)劃算法求解鋼條切割問(wèn)題
在應(yīng)用動(dòng)態(tài)規(guī)劃算法之前，我們先來(lái)看一下應(yīng)該如何去表示一段長(zhǎng)度為 n 米的鋼材切割問(wèn)題。首先，我們可以很清楚的知道一段長(zhǎng)度為 n 米的鋼條一共有 2n-1 種切割方案，因?yàn)樵阡摋l的第 1,2,3，…，n-1 米的位置，我們均可以選擇切割或者不切割。對(duì)于一段長(zhǎng)度為 n 米的鋼條，假設(shè)我們將他切割為 k 段，每一長(zhǎng)度段記為 i1，i2，…，ik 米，我們可以將切割方案記為 n= i1+i2+…+ik，對(duì)應(yīng)的收益 r (n) = p (i1) + p(i2) +… + p(ik)。接下來(lái)，我們按照上一節(jié)介紹的動(dòng)態(tài)規(guī)范算法的求解步驟來(lái)求解鋼條切割問(wèn)題。
- 步驟 1: 刻畫一個(gè)鋼條切割最優(yōu)解的結(jié)構(gòu)特征
根據(jù)之前描述的，在鋼條的第 1,2,3，…，n-1 米的位置，我們均可以選擇切割或者不切割?，F(xiàn)在我們考慮將一段長(zhǎng)度為 n 米鋼材切割的最大收益 r (n) 用小一點(diǎn)的鋼材收益表示，假設(shè)這個(gè)時(shí)候我們可以選擇切割一次或者不切割，那對(duì)應(yīng)著的 n 米的鋼材會(huì)有 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) 表示沒(méi)有切割，這樣我們就可以將計(jì)算一段長(zhǎng)度為 n 米的鋼材的最優(yōu)化切割方案轉(zhuǎn)換為小一點(diǎn)長(zhǎng)度的鋼材的最優(yōu)化切割方案。
在這里，我們可以注意到，為了求解規(guī)模為 n 的問(wèn)題，我們先求解形式完全一樣，單規(guī)模更小的問(wèn)題。當(dāng)完成首次切割之后，我們將兩段鋼材看出兩個(gè)獨(dú)立的鋼條切割問(wèn)題。我們通過(guò)組合兩個(gè)相關(guān)子問(wèn)題的最優(yōu)解，并在所有可能的兩段切割方案中選擇組合收益最大者，構(gòu)成原問(wèn)題的最優(yōu)解。我們稱鋼條切割問(wèn)題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)：?jiǎn)栴}的最優(yōu)解由相關(guān)子問(wèn)題的最優(yōu)解組合而成，而這些子問(wèn)題可以獨(dú)立求解。
- 步驟 2: 遞歸的定義鋼條切割的最優(yōu)解
當(dāng)我們清楚一個(gè)鋼條切割最優(yōu)解的結(jié)構(gòu)特征之后，現(xiàn)在開(kāi)始遞歸的定義鋼條切割的最優(yōu)解，我們先看一下前面幾種簡(jiǎn)單的鋼條切割的最優(yōu)解是什么樣的：
r (1) = 1，鋼條長(zhǎng)度為 1 米的鋼條最優(yōu)切割方法就是自身，因?yàn)橐呀?jīng)無(wú)法切割了
r (2) = 5，鋼條長(zhǎng)度為 2 米的鋼條切割方案有兩種， 1+1 或者 2，對(duì)應(yīng)的價(jià)值分別為 2 或 5，所以 r (2)=5
r (3) = 8，鋼條長(zhǎng)度為 3 米的鋼條切割方案有四種， 3,1+2,2+1，對(duì)應(yīng)的價(jià)值分別為 8,6,6，所以 r (3)=8
對(duì)應(yīng)步驟 1 中的鋼條切割問(wèn)題的最優(yōu)解的結(jié)構(gòu)特征，我們可以遞歸的定義鋼條切割問(wèn)題的最優(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)切割問(wèn)題的最優(yōu)解的定義之外，鋼條切割問(wèn)題還可以以另外一種相似的但是更為簡(jiǎn)單的方法去求解：將鋼條左邊切割下長(zhǎng)度為 i 米的一段，只對(duì)右邊剩下的長(zhǎng)度為 n-i 的一段進(jìn)行繼續(xù)切割（遞歸求解），對(duì)左邊的一段則不再進(jìn)行切割。
此時(shí)，問(wèn)題可以分解為：將長(zhǎng)度為 n 的鋼條分解為左邊開(kāi)始一段以及剩余部分繼續(xù)分解的結(jié)果。這樣，我可以得到對(duì)于上面公式的一個(gè)簡(jiǎn)化版本：
r(n) = max { p(i) + r(n-i) } , 1<= i <= n
至此，我們已經(jīng)完成了遞歸的定義鋼條切割問(wèn)題的最優(yōu)解；接下來(lái)，我們開(kāi)始計(jì)算最優(yōu)解的值。
- 步驟 3： 計(jì)算鋼條切割最優(yōu)解的值
考慮到對(duì)于長(zhǎng)度為 n 的鋼條切割的最優(yōu)解由其子問(wèn)題決定，我們可以先求解長(zhǎng)度較小的鋼條切割的最優(yōu)解，然后用較小長(zhǎng)度的最優(yōu)解去逐步求解長(zhǎng)度較大的鋼條切割的最優(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 行定義了一個(gè)新數(shù)組 r [0…n] 用來(lái)說(shuō)存儲(chǔ)子問(wèn)題的最優(yōu)解，第 3 行將 r [0] 初始化為 0，因?yàn)殚L(zhǎng)度為 0 的鋼條沒(méi)有收益。第 4 行到第 10 行是兩個(gè) for 循序，外層的 for 循環(huán)分別求解長(zhǎng)度為 i 的鋼條切割的最優(yōu)解，內(nèi)部的 for 循環(huán)是每一次求解最優(yōu)解的具體過(guò)程。
- 步驟 4： 利用計(jì)算出的信息構(gòu)造一個(gè)鋼條切割問(wèn)題的最優(yōu)解
前面的算法 CutSteelRod 可以計(jì)算出鋼條切割問(wèn)題通過(guò)動(dòng)態(tài)規(guī)劃算法計(jì)算出來(lái)的最優(yōu)解，但是并不會(huì)返回解本身（對(duì)應(yīng)的一個(gè)長(zhǎng)度列表，給出每段鋼條的切割長(zhǎng)度），如果我們需要得出具體的解，就需要對(duì)步驟 3 中的切割算法進(jìn)行重構(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 的子問(wèn)題時(shí)將第一段鋼條的最優(yōu)切割長(zhǎng)度 j 保存在 s [i] 中，詳見(jiàn)算法中的第 9 行。
4.JAVA 代碼實(shí)現(xiàn)
在說(shuō)明求解鋼條切割問(wèn)題的整個(gè)過(guò)程之后，接下來(lái)，我們看看如何用 java 代碼實(shí)現(xiàn)鋼條切割問(wè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("請(qǐng)輸入1到"+ (p.length-1)+"之間任意一個(gè)自然數(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("長(zhǎng)度為"+ n +"米長(zhǎng)的鋼材最大切割收益為："+r[n]);
System.out.println("對(duì)應(yīng)的具體每一段的切割長(zhǎng)度如下：");
while (n>0){
System.out.println(s[n]);
n = n - s[n];
}
}
運(yùn)行結(jié)果如下：
請(qǐng)輸入1到10之間任意一個(gè)自然數(shù):
8
長(zhǎng)度為8米長(zhǎng)的鋼材最大切割收益為：22
對(duì)應(yīng)的具體每一段的切割長(zhǎng)度如下：
2
6
運(yùn)行結(jié)果中首先需要輸入一個(gè)自然數(shù)表示要切割的鋼條的長(zhǎng)度，然后對(duì)應(yīng)輸出該長(zhǎng)度鋼條切割之后的最大化收益以及具體的切割方法。
代碼中第 8 行至第 10 行分別初始化對(duì)應(yīng)長(zhǎng)度的鋼材的價(jià)格表，對(duì)應(yīng)長(zhǎng)度鋼條切割之后的最大化收益數(shù)組，對(duì)應(yīng)長(zhǎng)度鋼條滿足最大化收益時(shí)第一次切割的長(zhǎng)度。代碼的第 15 行至第 25 行主要來(lái)實(shí)現(xiàn)步驟 4 中的 ExtendCutSteelRod 算法，用來(lái)計(jì)算最大化的切割收益及保存解，代碼的 27 行至 32 行主要是對(duì)求解結(jié)果的輸出。并且代碼中引用了 Scanner 類用來(lái)進(jìn)行交換處理，可以在控制臺(tái)輸入一段需要切割的鋼條長(zhǎng)度，然后返回對(duì)應(yīng)的切割結(jié)果。
5. 小結(jié)
本節(jié)主要學(xué)習(xí)了利用動(dòng)態(tài)規(guī)劃算法求解鋼條切割問(wèn)題，學(xué)習(xí)本節(jié)課程掌握鋼條切割問(wèn)題的算法流程，知道分動(dòng)態(tài)規(guī)劃算法是如何解決此類最優(yōu)化問(wèn)題，并且可以自己用代碼實(shí)現(xiàn)鋼條切割問(wèn)題的求解。在學(xué)習(xí)完本節(jié)課程之后，我們通過(guò)鋼條切割問(wèn)題這一實(shí)例介紹了動(dòng)態(tài)規(guī)劃算法的實(shí)際應(yīng)用，幫助大家可以更好的理解動(dòng)態(tài)規(guī)劃算法。
2025 imooc.com All Rights Reserved |