【動态規劃】鋼條切割問題

本人在學習《算法導論》的過程中，對于動态規劃這部分的内容不是特别了解，于是決定做一下學習與解決記錄，歡迎讨論交流。

文章目錄

• • • 0- 動态規劃問題的一般步驟
    • 1- 問題描述
    • 2-問題分析
    • 3-自頂向下遞歸實作
    • 4-使用動态規劃的方法求解
    • 5-重構解

0- 動态規劃問題的一般步驟

1- 刻畫一個最優解的結構特征

2- 遞歸定義最優解的值

3- 計算最優解的值，通常采用自底向上的方法

4- 利用計算出的資訊構造一個最優解

1- 問題描述

Serling 公司購買長鋼條，将其切割為鍛鋼條出售。切割工序本身沒有成本支出。公司管理層希望知道最佳的切割方案。

假定我們知道Serling公司出售一段長度為i英寸的鋼條的價格為pi(i = 1, 2,…,機關為美元)。鋼條的長度均為整英寸。下表給出了一個價格表的樣例。

長度i	1	2	3	4	5	6	7	8	9	10
價格p(i)	1	5	8	9	10	17	17	20	24	30

2-問題分析

鋼條切割問題是這樣的：給定一段長度為n英寸的鋼條和一個價格表p(i)(i = 1, 2,…,n),求切割鋼條方案，使得銷售收益rn最大。注意如果長度為n英寸的鋼條價格p(n)足夠大，最優解可能是完全不需要切割。

考慮n=4的情況。下圖給出了4英寸鋼條的所有可能切割方案，包括根本不切割的方案。從下圖可以看出，将一段長度為4英寸的鋼條切割為兩段各長為2英寸的鋼條，将産生p(2)+p(2)=5+5=10的收益，為最優解。

圖1 鋼條切割方案

對于最優收益rn(n≥1)可以用更短的鋼條的最優收益來描述：

r n = max(p n,r 1+r n-1,r 2+r n-2,...,r n-1+r 1)

第一個參數pn對應不切割，直接出售長度為n英寸的鋼條的方案。其中n-1個參數對應另外n-1種方案：對每個i = 1, 2, …, n-1,首先将鋼條切割為i和n-i的兩段，接着求解這兩段的最優切割收益ri和rn -i（每種方案的最優收益為兩段的最優收益之和）。由于無法預知那種方案的将獲得最佳收益，是以必須考慮所有可能的i，選取其中的收益最大者。如果直接出售圓鋼條會獲得最大收益，當然可以不做任何切割。

可以看出，通過組合兩個子問題（完成首次切割之後，即将問題轉化為求解兩個獨立的鋼條切割問題執行個體）的最優解，并在所有可能得兩段切割方案中選取組合收益最大者，構成原問題的最優解。

鋼條問題是滿足最優子結構的（optimal substructure） 性質的：問題的最優解由相關子問題的最優解組合而成，而且這些子問題可以獨立求解。

3-自頂向下遞歸實作

簡單的遞歸求解方法： 将鋼條從左邊切割下長度為i的一段，隻對右邊剩餘的長度為n-i的一段繼續進行切割（遞歸求解），對左邊的一段則不再進行切割。問題的分解方式為：将長度為n的鋼條分解為左邊的開始一段，以及剩餘部分繼續分解的結果。這樣，不做任何切割的方案可以描述為：第一段的長度為你n，收益為pn，剩餘部分的長度為0，對應的收益r0=0。 于是可以得到如下公式：

r n = max(p i +r n-i)

原問題的最優解隻包含一個相關子問題（右邊剩餘部分）的解。下面給出樸素遞歸算法的解：

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>

using namespace std;

vector<int> price{1, 5, 8, 9, 10, 17, 17, 20, 24, 30};//鋼條對應的價格

int CutRod(vector<int> &price, int length){
    if(length == 0) return 0;//如果鋼條長度為0，直接傳回
    int maxvalue = INT_MIN;//因為鋼條價格為正值，是以首先預設maxvalue為最小值
    for(int i = 1; i <= length; ++i){
    //取前一次疊代算得的maxvalue與本次疊代結果的最大值
    //疊代：目前鋼條段的價值 + 剩餘右邊鋼條的價值
    //（這裡因為下标從0開始，是以有-1）
        maxvalue = max(maxvalue, price[i - 1] + CutRod(price, length - i));
    }
    return maxvalue;
}
int main() {
    int length = 0;
    cin >> length;
    cout << "maxvalue: " << CutRod(price,length)<<endl;
    return 0;
}
           

以上利用純遞歸調用的方法效率很差，運作時間會呈爆炸性增長。可以取n = 4繪制遞歸調用樹進行觀察：

圖2 n = 4的遞歸調用樹

這棵遞歸調用樹共有2n個結點， 其中有2n-1 個葉結點。

4-使用動态規劃的方法求解

動态規劃有兩種等價的實作方法：

1- 帶備忘錄的自頂向下法（top-down with memoization） ：此方法仍然按照自然的遞歸形式編寫，但過程會儲存每個子問題的解。當需要一個子問題的解時，過程首先檢查是否已經儲存過此解。如果是，則直接傳回儲存的值，進而節省了計算時間；否則，按通常方式計算這個子問題。

2-自底向上法（bottom-up method）：這種問題一般需要恰當定義子問題的“規模”的概念，使得任何子問題的求解都隻依賴于“更小的”子問題的求解。因而我們可以将子問題按規模排序，按由小到大的順序進行求解。當求解某個子問題時，它依賴的那些更小的子問題都已求解完畢，結果已經儲存。每個子問題隻需求解一次，當我們求解該問題時（第一次遇到），其所有的子問題均已求解完畢。

• 帶備忘錄的自頂向下法，備忘機制

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>

using namespace std;

vector<int> price{1, 5, 8, 9, 10, 17, 17, 20, 24, 30};//鋼條對應的價格

int MemoCutRodAux(vector<int> &price,vector<int> &memoprice,int cutlength){
    int  maxvalue = INT_MIN;
    if(memoprice[cutlength] >= 0){
        return memoprice[cutlength];//入口進行檢查，看所需值是否已知，如果是，則直接傳回儲存的值
    }     
    if(cutlength == 0) { maxvalue = 0; }
    else{
        for(int j = 1; j <= cutlength; ++j){
            maxvalue = max(maxvalue, price[j - 1] + MemoCutRodAux(price, memoprice, cutlength - j));
        }
    }
    memoprice[cutlength] = maxvalue;
    return memoprice[cutlength];
}

int MemoCutRod(vector<int> &price,int length){
    vector<int> memoprice{};
    for(int i = 0; i <= length; ++i){//特别注意的是，備忘錄是包含長度為0的情況的，是以範圍是[0,length]
        memoprice.push_back(INT_MIN);//已知收益非負，是以可以這樣處理“未知值”
    }
    return  MemoCutRodAux(price,memoprice,length);
}

int main() {
    int length = 0;
    cin >> length;
    cout << "MemoCutRod maxvalue: " << MemoCutRod(price,length)<<endl;
    return 0;
}
           

• 自底向上方法：采用子問題的自然順序，若i < j，則規模為i的子問題比規模為j的子問題“更小”，是以過程依次求解規模為j= 0, 1， …， n的子問題

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>

using namespace std;

vector<int> price{1, 5, 8, 9, 10, 17, 17, 20, 24, 30};//鋼條對應的價格

int BottomUpCutRod(vector<int> &price, int length){
    vector<int> value(length + 1);
    value[0] = 0;//長度為0即沒有收益

    for(int j = 1; j <= length; ++j){
        int maxvalue = INT_MIN;
        for(int i = 1; i <= j; ++i){
            maxvalue = max(maxvalue,price[i - 1] + value[j - i]);//直接通路存好的解，來獲得j-i這一子問題的解，省去了遞歸調用
        }
        value[j] = maxvalue;//規模為j的子問題的解直接存入
    }
    return value[length];

}

int main() {
    int length = 0;
    cin >> length;
    cout << "BottomUpCutRod maxvalue: " << BottomUpCutRod(price,length)<<endl; 
    return 0;
}
           

5-重構解

上面的解決方法中知識傳回了切割問題的最優解的收益值，但并沒有傳回解本身（一個長度清單，給出切割後每段鋼條的長度）。下面對算法進行擴充，以輸出最優解的切割方案：

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>

using namespace std;

vector<int> price{1, 5, 8, 9, 10, 17, 17, 20, 24, 30};//鋼條對應的價格

typedef struct {//結構體進行資料儲存
    vector<int> value{};
    vector<int> cutlen{};
}stResult;

stResult ExtendedBottomUpCutRod(vector<int> &price, int length){
    stResult stresult;
    vector<int> valuetmp(length + 1);
    vector<int> cutlentmp(length + 1);
    stresult.value = valuetmp;
    stresult.cutlen = cutlentmp;
    stresult.value[0] = 0;

    for(int j = 1; j <= length; ++j){
        int maxvalue = INT_MIN;
        for (int i = 1; i <= j; ++i){
            if( maxvalue < price[ i -1] + stresult.value[j - i]){
                maxvalue = price[ i -1] + stresult.value[j - i];
                stresult.cutlen[j] = i;//儲存最優切割方案
            }
        }
        stresult.value[j] = maxvalue;
    }
    return stresult;
}

int main() {
    int length = 0;
    cin >> length;
    stResult stresult = ExtendedBottomUpCutRod(price,length);

    while(length > 0){
        cout<<stresult.cutlen[length]<<" ";//輸出最佳切割方案
        length = length - stresult.cutlen[length];
    }
    return 0;
}
           

對上面的解決方案，

ExtendedBottomUpCutRod(price,10)

會傳回如下的表格：

i	1	2	3	4	5	6	7	8	9	10
value[i]	1	5	8	10	13	17	18	22	25	30
cutlen[i]	1	2	3	2	2	6	1	2	3	10

PS：公衆号上線啦，技術幹貨分享，歡迎關注。