算法導(dǎo)論筆記動(dòng)態(tài)規(guī)劃DP詳解-鋼條切割的分析與實(shí)現(xiàn)

shinezejian 發(fā)布于2019-08-14 17:51 / 3218人閱讀

摘要：假定出售一段長(zhǎng)度為英寸的鋼條的價(jià)格為單位，鋼條長(zhǎng)度均為整英寸。注若長(zhǎng)度為英寸的鋼條的價(jià)格足夠大，最優(yōu)解可能就是完全不需要切割。考慮長(zhǎng)度為的情況，下圖給出了英寸鋼條的所有切割方案。

DP和分治的相似

都是通過組合子問題的解來(lái)求解原問題。

DP中的“programming”指的是一種表格法，而非coding。

DP和分治的不同

分治步驟：（例如歸并排序）

將問題劃分為互不相交的子問題

遞歸地求解子問題

組合子問題的解，求出原問題的解

對(duì)于DP：

應(yīng)用于子問題重疊的情況，即不同的子問題具有公共的子子問題（子問題的求解是遞歸進(jìn)行的，將其劃分為更小的子子問題）

這種情況下分治會(huì)做很多不必要的工作，會(huì)反復(fù)求解哪些公共子問題。

而DP對(duì)每個(gè)子子問題只求解一次，將其解保存在一個(gè)表格中，無(wú)需每次都重新計(jì)算，避免重復(fù)工作。

DP通常用來(lái)求解最優(yōu)化問題（optimization problem）

這種問題可以有很多可行的解，每個(gè)解都有一個(gè)值，希望找到最優(yōu)值（最大或最小）的解。稱這樣的解為問題的一個(gè)最優(yōu)解（an optimal solution）,而不是最優(yōu)解（the optimal solution）,因?yàn)榭赡苡卸鄠€(gè)解都達(dá)到最優(yōu)。

DP的四個(gè)步驟

刻畫一個(gè)最優(yōu)解的結(jié)構(gòu)特征。

遞歸地定義最優(yōu)解的值。

計(jì)算最優(yōu)解的值，通常采用自底向上法。

利用計(jì)算出的信息構(gòu)造一個(gè)最優(yōu)解。

前三步是DP求解的基礎(chǔ)。若僅需要一個(gè)最優(yōu)解的值，而非解本身，可忽略第四步。若需第四步，有時(shí)需在執(zhí)行第3步的過程中維護(hù)一些額外的信息，以便構(gòu)造一個(gè)最優(yōu)解。

鋼條切割例子

場(chǎng)景：把長(zhǎng)鋼條切割為短鋼條出售。切割工序本身無(wú)成本。求最佳切割方案。

假定：出售一段長(zhǎng)度為 i 英寸的鋼條的價(jià)格為Pi(i = 1, 2, …, )單位:$，鋼條長(zhǎng)度均為整英寸。下圖為價(jià)格表。

問題描述：給定一段長(zhǎng)度為n英寸的鋼條和一個(gè)價(jià)格表，求切割方案，使銷售收益Rn最大。注：若長(zhǎng)度為n英寸的鋼條的價(jià)格Pn足夠大，最優(yōu)解可能就是完全不需要切割。

考慮長(zhǎng)度為4的情況，下圖給出了4英寸鋼條的所有切割方案。

切成兩段各長(zhǎng)2英寸的鋼條，將產(chǎn)生P2 + P2 = 5 + 5 = 10 的收益，為最優(yōu)解。

長(zhǎng)度為n英寸的鋼條共有2^(n-1)種不同切割方案，因?yàn)樵诰嚯x鋼條左端 i (i=1, 2, … , n-1)英寸處，總是可以選擇切割或者不切割。用普通的加法符號(hào)表示切割方案，因此7=2+2+3表示將長(zhǎng)度為7的鋼條切割為3段：2英寸，2英寸，3英寸。

若一個(gè)最優(yōu)解將鋼條切割為k段（1≤k≤n），那么最優(yōu)切割方案 n = i1 + i2 + … + ik.

將鋼條切割為長(zhǎng)度分別為i1, i2, … , ik的小段，得到的最大收益為 Rn = Pi1 + Pi2+…+Pik

對(duì)于上面表格的價(jià)格樣例，可以觀察所有最優(yōu)收益值Ri (i: 1~10)以及最優(yōu)方案：

長(zhǎng)度為1：切割方案1=1（無(wú)切割）。最大收益R1 = 1

長(zhǎng)度為2：切割方案2=2（收益5），1+1=2（收益2）。最大收益R2 = 5

長(zhǎng)度為3：切割方案3=3（收益8），1+2=3（收益6），2+1=3（收益6）。最大收益8

長(zhǎng)度為4：切割方案4=4（收益9），1+3=4（收益9），2+2=4（收益10），3+1=4（收益9），1+1+2=4（收益7），1+2+1=4（收益7），2+1+1=4（收益7），1+1+1+1=4（收益4）。最大收益10

長(zhǎng)度為5：切割方案5=5（10），1+4=5（10），2+3=5（13），1+1+3=5（10），2+2+1=5（11），1+1+1+1+1=5（5），其他是前面的排列。最大收益13

依次求出。。。

更一般的，對(duì)于Rn(n≥1)，可以用更短的鋼條的最優(yōu)切割收益來(lái)描述它：

Rn = max(Pn, R1+Rn-1, R2 + Rn-2, … , Rn-1 + R1)

第一個(gè)參數(shù)Pn對(duì)應(yīng)不切割，直接出售長(zhǎng)度為n的方案。

其他n-1個(gè)參數(shù)對(duì)應(yīng)n-1種方案。對(duì)每個(gè)i=1,2,….,n-1，將鋼條切割為長(zhǎng)度為i和n-i的兩段，接著求解這兩段的最優(yōu)切割收益Ri和Rn-i;(每種方案的最優(yōu)收益為兩段的最優(yōu)收益之和)。

由于無(wú)法預(yù)知哪種方案會(huì)獲得最優(yōu)收益，必須考察所有可能的 i ，選取其中收益最大者。若不切割時(shí)收益最大，當(dāng)然選擇不切割。

注意到：

為了求解規(guī)模為n的原問題，先求解子問題（子問題形式完全一樣，但規(guī)模更小）。

即首次完成切割后，將兩段鋼條看成兩個(gè)獨(dú)立的鋼條切割問題實(shí)例。

通過組合兩個(gè)相關(guān)子問題的最優(yōu)解，并在所有可能的兩段切割方案中獲取收益最大者，構(gòu)成原問題的最優(yōu)解。

稱鋼條切割問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)：

問題的最優(yōu)解由相關(guān)子問題的最優(yōu)解組合而成，而這些子問題可以獨(dú)立求解。

除上述解法，問題可化簡(jiǎn)為一種相似的遞歸：從左邊切割下長(zhǎng)度為 i 的一段，只對(duì)右邊剩下的長(zhǎng)度為 n-i 的一段進(jìn)行繼續(xù)切割（遞歸求解），對(duì)左邊一段則不再進(jìn)行切割。

即問題分解的方式為：將長(zhǎng)度為n的鋼條分解為左邊開始一段，以及剩余部分繼續(xù)分解的結(jié)果。（這樣，不做任何切割的方案可以描述為：第一段長(zhǎng)度為n，收益為Pn，剩余部分長(zhǎng)度為0，對(duì)應(yīng)收益為R0 = 0）。于是得到上面公式的簡(jiǎn)化版本：

在此公式中，原問題的最優(yōu)解只包含一個(gè)相關(guān)子問題（右端剩余部分的解），而不是兩個(gè)。

自頂向下遞歸實(shí)現(xiàn)的偽代碼：Cut-Rod(p, n)

Cut-Rod(p, n)
1    if n==0
2        return 0
3    q = -∞
4    for i = 1 to n
5        q = max(q, p[i] + Cut-Rod(p, n-i))
6    return q

該過程以價(jià)格數(shù)組p[1...n]和整數(shù)n為輸入，返回長(zhǎng)度為n的鋼條的最大收益。

若n=0，不可能有任何收益，所以第二行返回0.

第3行將最大收益初始化為負(fù)無(wú)窮，以便第4第5行的for循環(huán)能正確計(jì)算。

第6行返回結(jié)果。Java實(shí)現(xiàn)如下：

/**
 * 鋼條切割
 */
public class CutRob {
    public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
    public static int solution(int length){
        if(length == 0)    return 0;
        int result = Integer.MIN_VALUE;
        for(int i = 1; i <= length; i++){
            result = Math.max(result, prices[i-1] + solution(length-i));
        }
        return result;
    }
    public static void main(String[] args) {
        for(int i=1; i<= prices.length; i++)
            System.out.println("長(zhǎng)度為"+i+"的最大收益為："+solution(i));
    }
}

結(jié)果：

長(zhǎng)度為1的最大收益為：1
長(zhǎng)度為2的最大收益為：5
長(zhǎng)度為3的最大收益為：8
長(zhǎng)度為4的最大收益為：10
長(zhǎng)度為5的最大收益為：13
長(zhǎng)度為6的最大收益為：17
長(zhǎng)度為7的最大收益為：18
長(zhǎng)度為8的最大收益為：22
長(zhǎng)度為9的最大收益為：25
長(zhǎng)度為10的最大收益為：30

該遞歸很好理解，但是一旦規(guī)模較大，程序運(yùn)行時(shí)間會(huì)暴漲，課本上說(shuō)對(duì)n=40要好幾分鐘，很可能超過1小時(shí)，本次實(shí)驗(yàn)一下n=33. (假設(shè)從鋼條長(zhǎng)度超過10開始價(jià)格就一直保持在30美元)

public class CutRob {
    public static int[] prices = 
            {1,5,8,9,10,17,17,20,24,30,
            30,30,30,30,30,30,30,30,30,30,
            30,30,30,30,30,30,30,30,30,30,
            30,30,30};
//    public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
    public static int solution(int length){
        if(length == 0)    return 0;
        int result = Integer.MIN_VALUE;
        for(int i = 1; i <= length; i++){
            result = Math.max(result, prices[i-1] + solution(length-i));
        }
        return result;
    }
    public static void main(String[] args) {
        long curr = System.currentTimeMillis();
        System.out.println("長(zhǎng)度為33的最大收益為："+solution(33));
        System.out.println(System.currentTimeMillis() - curr);
    }
}

長(zhǎng)度為33的最大收益為：98
25507

該遞歸計(jì)算結(jié)果用了幾乎26秒。當(dāng)輸入長(zhǎng)度繼續(xù)增大，會(huì)消耗更長(zhǎng)的時(shí)間。

為什么效率這么差？原因在于，CutRob反復(fù)的用相同的參數(shù)值對(duì)自身進(jìn)行遞歸調(diào)用，即反復(fù)的求解子問題。

下圖顯示了n=4時(shí)的調(diào)用過程CutRob(p, n)對(duì)i=1,2,…,n調(diào)用CutRob( p,n-i )，等價(jià)于對(duì)j=0,1,…,n-1調(diào)用CutRob( p, j )，該遞歸展開時(shí)，所做的工作量會(huì)爆炸性增長(zhǎng)。

為了分析該算法運(yùn)行時(shí)間，令T(n)表示第二個(gè)參數(shù)值為n時(shí)函數(shù)的調(diào)用次數(shù)。此值等于遞歸調(diào)用樹中根為n的子樹中的節(jié)點(diǎn)總數(shù)，注意，此值包含了根節(jié)點(diǎn)對(duì)應(yīng)的最初的一次調(diào)用。因此T(0)=1,且

第一項(xiàng) ’1’ 表示函數(shù)的第一次調(diào)用（遞歸調(diào)用樹的根節(jié)點(diǎn)），T( j )為調(diào)用cutrob(p, n-i)所產(chǎn)生的所有調(diào)用次數(shù)。T(n) = 2^n。即該算法的運(yùn)行時(shí)間為n的指數(shù)函數(shù)。

回頭看下，該運(yùn)行時(shí)間并不令人驚訝。對(duì)于長(zhǎng)度為n的鋼條，該算法顯然考察了所有2^(n-1)種可能的切割方案。遞歸調(diào)用樹中共有2^(n-1)個(gè)葉子節(jié)點(diǎn)，每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)一種可能的切割方案。對(duì)每條從根到葉子的路徑，路徑上的標(biāo)號(hào)給出了每次切割前右邊剩余部分的長(zhǎng)度（子問題規(guī)模）。也就是說(shuō)，標(biāo)號(hào)給出了對(duì)應(yīng)的切割點(diǎn)（從鋼條右端測(cè)量）。

看完了遞歸解法以及其暴漲的復(fù)雜度。下面來(lái)看下用DP怎么來(lái)解決鋼條切個(gè)問題。思想如下：

已經(jīng)看到，樸素遞歸算法之所以效率低，是因?yàn)榉磸?fù)求解相同的子問題。

DP會(huì)仔細(xì)安排求解順序，對(duì)每個(gè)子問題只求解一次，并將結(jié)果保存下來(lái)。如果隨后再次需要次子問題的解，只需查找保存的結(jié)果，而不必重新計(jì)算。

因此DP用空間來(lái)節(jié)省時(shí)間。是典型的時(shí)空權(quán)衡例子（time-memory trade-off）。

如果子問題數(shù)量是輸入規(guī)模的多項(xiàng)式函數(shù)，則可以在多項(xiàng)式時(shí)間內(nèi)求解出每個(gè)子問題。其總時(shí)間復(fù)雜度就是多項(xiàng)式階的。

DP有兩種等價(jià)的實(shí)現(xiàn)方法：帶備忘的自頂向下法（top-down with memoization）& 自底向上法（bottom-up method）。

帶備忘的自頂向下法（top-down with memoization）

此方法仍然按照自然的遞歸形式編寫過程，但是過程會(huì)保存每個(gè)子問題的解（通常保存在一個(gè)數(shù)組或散列表中）。

當(dāng)需要一個(gè)子問題的解時(shí)，過程首先檢查是否已經(jīng)保存過此解，

如果是，則直接返回保存的值，從而節(jié)省了計(jì)算時(shí)間；

否則，按照通常方式計(jì)算這個(gè)子問題。

自底向上法（bottom-up method）

該方法一般需要恰當(dāng)定義子問題“規(guī)?！钡母拍睿沟萌魏巫訂栴}的求解都只依賴于“更小的”子問題的求解。

因而可以將子問題按規(guī)模排序，按由小到大的順序進(jìn)行求解。

當(dāng)求解某個(gè)子問題時(shí)，所依賴的那些更小的子問題都已經(jīng)求解完畢，結(jié)果已經(jīng)保存。

每個(gè)子問題只求解一次，當(dāng)求解它時(shí)（也是第一次遇到它），所有前提子問題都已經(jīng)求解完成。

兩種方法得到的算法具有相同的漸進(jìn)運(yùn)行時(shí)間，

僅有的差異是在某些特殊情況下，自頂向下方法并未真正遞歸地考察所有可能的子問題。

由于沒有頻繁的遞歸調(diào)用開銷，自底向上的復(fù)雜度函數(shù)通常具有更小的系數(shù)。

算法偽代碼-帶備忘的自頂向下法（top-down with memoization）

mem-cut-rod(p, n)
1    let r[0…n] be a new array
2    for i=0 to n
3        r[i] = -∞
4    return mem-cut-rod-aux(p, n, r)

mem-cut-rod-aux(p, n, r)
1    if r[n] >= 0
2        return r[n]
3    if n == 0
4        q = 0
5    else 
6        q = -∞
7        for i=1 to n
8            q = max(q, p[i] + mem-cut-rod-aux(p, n-i, r))
9    r[n] = q
10   return q

主過程 mem-cut-rod(p, n)將輔助數(shù)組r[0...n]初始化為負(fù)無(wú)窮，然后調(diào)用輔助過程mem-cut-rod-aux(最初cut-rob引入備忘機(jī)制的版本)。偽代碼解讀：

首先檢查所需值是否已知（第1行）;
如果是，則第2行直接返回保存的值;
否則第3~8行用通常方法計(jì)算所需值q;
第9行將q存入r[n]中;
第10行返回;

自底向上版本更簡(jiǎn)單：

bottom-up-cut-rod(p, n)
1    let r[0…n] be a new array
2    r[0] = 0
3    for j=1 to n
4        q = -∞
5        for i=1 to j
6            q = max(q, p[i] + r[j-i])
7        r[j] = q
8    return r[n]

自底向上版本采用子問題的自然順序：若i

第1行創(chuàng)建一個(gè)新數(shù)組r[0...n]來(lái)保存子問題的解；
第2行將r[0]初始化為0，因?yàn)殚L(zhǎng)度為0的鋼條沒有收益；
第3~6行對(duì)j=1...n按升序求解每個(gè)規(guī)模為j的子問題。求解方法與cut-rod采用的方法相同，只是現(xiàn)在直接訪問數(shù)組元素r[j-i]來(lái)獲取規(guī)模為j-i的子問題的解，而不必進(jìn)行遞歸調(diào)用；
第7行將規(guī)模為 j 的子問題的解存入r[j]；
第8行返回r[n],即最優(yōu)解

兩種方法具有相同的漸進(jìn)運(yùn)行時(shí)間。

bottom-up-cut-rod 主體是嵌套的雙層循環(huán)，內(nèi)層循環(huán)（5~6行）的迭代次數(shù)構(gòu)成一個(gè)等差數(shù)列和，不難分析時(shí)間為n^2.

mem-cut-rod 運(yùn)行時(shí)間也是n^2，其分析略難：當(dāng)求解一個(gè)之前已經(jīng)計(jì)算出結(jié)果的子問題時(shí)，遞歸調(diào)用會(huì)立即返回，即每個(gè)子問題只求解一次，而它求解了規(guī)模為0，1，。。。，n的子問題；為求解規(guī)模為n的子問題，第6~7行的循環(huán)會(huì)迭代n次；因此進(jìn)行的所有遞歸調(diào)用執(zhí)行此for循環(huán)的迭代次數(shù)也是一個(gè)等差數(shù)列，其和也是n^2。

Java實(shí)現(xiàn)：

public class CutRob {
    public static int[] prices = {1,5,8,9,10,17,17,20,24,30};    
    /** 自頂向下*/
    public static int mem_cut_rod(int n){
        int[] dp = new int[n+1];            // 輔助數(shù)組dp
        Arrays.fill(dp, Integer.MIN_VALUE);  // 初始化為負(fù)無(wú)窮
        return mem_cut_rod_aux(n, dp);
    }
    /** 自頂向下法的輔助函數(shù)*/
    private static int mem_cut_rod_aux(int n, int[] dp) {
        if(dp[n] >= 0)    return dp[n]; // 如果子問題已經(jīng)解過，直接返回
        int max = Integer.MIN_VALUE;
        if(n==0)    max = 0;          // 如果長(zhǎng)度為0，則最大收益為0
        else{                        // 長(zhǎng)度若不為0
            for(int i = 1; i<=n; i++)    // 找到最大收益
                max = Math.max(max, prices[i-1] + mem_cut_rod_aux(n-i, dp));
        }
        dp[n] = max;            // 把計(jì)算得到的最大收益存入結(jié)果
        return max;                // 返回結(jié)果
    }

    public static void main(String[] args) {
        for(int i=1; i<=prices.length; i++)
            System.out.println("長(zhǎng)度為"+i+"的最大收益為："+mem_cut_rod(i));
    }
}


長(zhǎng)度為1的最大收益為：1
長(zhǎng)度為2的最大收益為：5
長(zhǎng)度為3的最大收益為：8
長(zhǎng)度為4的最大收益為：10
長(zhǎng)度為5的最大收益為：13
長(zhǎng)度為6的最大收益為：17
長(zhǎng)度為7的最大收益為：18
長(zhǎng)度為8的最大收益為：22
長(zhǎng)度為9的最大收益為：25
長(zhǎng)度為10的最大收益為：30

自底向上：

public class CutRob {
    public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
        /** 自底向上法*/
    private static int bottom_up_cut_rod(int n){
        int[] dp = new int[n+1];
        dp[0] = 0;
        for(int j=1; j<=n; j++){
        int max = Integer.MIN_VALUE;
        for(int i=1; i<=j; i++){
            max = Math.max(max, prices[i-1] + dp[j-i]);
        }
        dp[j] = max;
        }
        return dp[n];
    }
    public static void main(String[] args) {
        for(int i=1; i<=prices.length; i++)
            System.out.println("長(zhǎng)度為"+i+"的最大收益為："+bottom_up_cut_rod(i));
    }
}

下面來(lái)從運(yùn)行結(jié)果的時(shí)間上做一個(gè)對(duì)比，這里拿自底向上法來(lái)和前面的遞歸做對(duì)比。

上面的樸素遞歸只把輸入的n增加到33，就運(yùn)行了25507毫秒。下面來(lái)看下自底向上。

public class CutRob {
    public static int[] prices = 
            {1,5,8,9,10,17,17,20,24,30,
            30,30,30,30,30,30,30,30,30,30,
            30,30,30,30,30,30,30,30,30,30,
            30,30,30,30,30,30,30,30,30,30,
            30,30,30,30,30,30,30,30,30,30,
            30,30,30};
//    public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
    /** 自底向上法*/
    private static int bottom_up_cut_rod(int n){
        int[] dp = new int[n+1];
        dp[0] = 0;
        for(int j=1; j<=n; j++){
            int max = Integer.MIN_VALUE;
            for(int i=1; i<=j; i++){
                max = Math.max(max, prices[i-1] + dp[j-i]);
            }
            dp[j] = max;
        }
        return dp[n];
    }
    public static void main(String[] args) {
        long curr = System.currentTimeMillis();
        System.out.println(“長(zhǎng)度為53的最大收益為："+bottom_up_cut_rod(53));
        System.out.println(System.currentTimeMillis() - curr);
    }
}

用自底向上把輸入增加到53，整個(gè)過程也就運(yùn)行了1毫秒。

輸出：
長(zhǎng)度為53的最大收益為：158
1

子問題圖：

當(dāng)思考一個(gè)DP問題時(shí)，應(yīng)弄清楚所涉及的子問題以及子問題之間的依賴關(guān)系。

問題的子問題圖準(zhǔn)確的表達(dá)了這些信息。下圖展示了n=4時(shí)鋼條切割問題的子問題圖。

它是一個(gè)有向圖，每個(gè)頂點(diǎn)唯一對(duì)應(yīng)一個(gè)子問題。

若求子問題x的最優(yōu)解時(shí)需要直接用到子問題y的最優(yōu)解，那么在子問題圖中就會(huì)有一條從子問題x的頂點(diǎn)到子問題y的頂點(diǎn)的有向邊。

例如，若自頂向下過程在求解x時(shí)需要直接遞歸調(diào)用自身來(lái)求解y，那么子問題圖就包含從x到y(tǒng)的一條有向邊。

可以將子問題圖看做自頂向下遞歸調(diào)用樹的“簡(jiǎn)化版”或“收縮版”，因?yàn)闃渲兴袑?duì)應(yīng)相同子問題的節(jié)點(diǎn)合并為圖中的單一頂點(diǎn)，相關(guān)的所有邊都從父節(jié)點(diǎn)指向子節(jié)點(diǎn)。

自底向上的DP方法處理子問題圖中頂點(diǎn)的順序?yàn)椋簩?duì)于一個(gè)給定的子問題x，在求解它之前求解鄰接至它的子問題y。

用22章的術(shù)語(yǔ)說(shuō)，自底向上動(dòng)態(tài)規(guī)劃算法是按“逆拓?fù)渑判颉被蛘摺胺葱虻耐負(fù)渑判颉眮?lái)處理子問題圖中的頂點(diǎn)。

換句話說(shuō)，對(duì)于任何子問題，直至它所依賴的所有子問題均已求解完成，才會(huì)求解它。

類似的，可以用22章中的術(shù)語(yǔ)“深搜”來(lái)描述（帶備忘機(jī)制的）自頂向下動(dòng)態(tài)規(guī)劃算法處理子問題圖的順序。（22.3節(jié)）

子問題圖G = ( V, E )的規(guī)?？梢詭椭覀兇_定DP算法的運(yùn)行時(shí)間。

由于每個(gè)子問題只求解一次，因此算法運(yùn)行時(shí)間等于每個(gè)子問題求解時(shí)間之和。

通常，一個(gè)子問題的求解時(shí)間與子問題圖中對(duì)應(yīng)頂點(diǎn)的度（出射邊的數(shù)目）成正比，而子問題的數(shù)目等于子問題圖的頂點(diǎn)數(shù)。

因此，DP算法運(yùn)行時(shí)間與頂點(diǎn)和邊的數(shù)量成線性關(guān)系。

重構(gòu)解

前文給出的鋼條切割DP算法返回最優(yōu)解的收益值，并未返回解本身（一個(gè)長(zhǎng)度列表，給出切割后每段鋼條的長(zhǎng)度）。

我們可以擴(kuò)展DP算法，使之對(duì)于每個(gè)問題不僅保存最優(yōu)收益值，還保存對(duì)應(yīng)的切割方案。利用這些信息，就能輸出最優(yōu)解。

下面給出bottom-up-cut-rob的擴(kuò)展版本，它對(duì)于長(zhǎng)度為j 的鋼條不僅計(jì)算最大收益值Rj, 還保存最優(yōu)解對(duì)應(yīng)的第一段鋼條的切割長(zhǎng)度Sj：

extended-bottom-up-cut-rod(p, n)
1    let r[0…n] and s[0…n] be new arrays
2    r[0] = 0
3    for j=1 to n
4        q = -∞
5        for i=1 to j
6            if q < p[i]+r[j-i]
7                q = p[i]+r[j-i]
8                s[j] = i
9        r[j] = q
10    return r and s

此過程和bottom-up-cut-rob很相似，差別只是在第1行創(chuàng)建了數(shù)組s，并在求解規(guī)模為j的子問題時(shí)，將第一段鋼條的最優(yōu)切割長(zhǎng)度i保存在s[ j ]中（第8行）。

下面的過程接受兩個(gè)參數(shù)：價(jià)格表p和鋼條長(zhǎng)度n，然后調(diào)用extended-bottom-up-cut-rod來(lái)計(jì)算切割下來(lái)的每段鋼條的長(zhǎng)度s[1...n]，最后輸出長(zhǎng)度為n的鋼條的完整的最優(yōu)切割方案：

print-cut-rob-solution(p, n)
1    (r, s) = extended-bottom-up-cut-rod(p, n)
2    while n>0
3        print s[n]
4        n = n-s[n]

對(duì)于前文給出的鋼條切割實(shí)例，extended-bottom-up-cut-rod(p, 10)會(huì)返回下面的數(shù)組：

這個(gè)表一定要根據(jù)代碼邏輯親手畫一遍。體會(huì)其構(gòu)建過程。

i 0 1 2 3 4 5 6 7 8 9 10
r [ i ] 0 1 5 8 10 13 17 18 22 25 30
s [ i ] 0 1 2 3 2 2 6 1 2 3 10

對(duì)此例調(diào)用print-cut-rod-solution(p,10)只會(huì)輸出10，但對(duì)n=7，會(huì)輸出最優(yōu)方案R7切割出的兩段鋼條長(zhǎng)度1和6。看看Java代碼實(shí)現(xiàn)：

public class CutRob {
    public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
    private static int[] path; 
    /** 帶切割方案的自底向上擴(kuò)展方案*/
    public static int extended_bottom_up_cut_rod(int n){
        int[] dp = new int[n+1];
        path = new int[n+1];
        dp[0] = 0;
        for(int j = 1; j<=n; j++){
            int max = Integer.MIN_VALUE;
            for(int i=1; i<=j; i++){
                if(max < (prices[i-1] + dp[j-i])){
                    max = prices[i-1] + dp[j-i];
                    path[j] = i;
                }
            }
            dp[j] = max;
        }
        return dp[n];
    }
    /** 得到切割方案(一個(gè)最優(yōu)解)*/
    public static ArrayList getACutSolution(int n){
        ArrayList result = new ArrayList<>();
        while(n > 0){
            result.add(path[n]);
            n -= path[n];
        }
        return result;
    }
    public static void main(String[] args) {
        System.out.println("長(zhǎng)度為7的最大收益為："+extended_bottom_up_cut_rod(7));
        System.out.println(getACutSolution(7));
    }
}

輸出：
長(zhǎng)度為7的最大收益為：18
[1, 6]

至此，對(duì)DP有了一個(gè)剛剛開始的了解。

GPU云服務(wù)器云服務(wù)器中SP與DP的區(qū)別 r數(shù)據(jù)分析方法與案例詳解算法導(dǎo)論算法導(dǎo)論答案

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/66846.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

shinezejian

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

#黑五#hostarmada：共享主機(jī)80%折扣，vps主機(jī)30%折扣，新加坡/美國(guó)等9機(jī)房

閱讀 964·2021-11-24 10:42
面試官問我Redis集群，我真的是

閱讀 3475·2021-11-19 11:34
C語(yǔ)言進(jìn)階：動(dòng)態(tài)內(nèi)存管理

閱讀 2605·2021-09-29 09:35
干貨|app自動(dòng)化測(cè)試之Andriod WebView如何測(cè)試

閱讀 2525·2021-09-09 09:33
2020騰訊云產(chǎn)品采購(gòu)季有獎(jiǎng)問卷調(diào)查,認(rèn)真填寫送騰訊云代金券獎(jiǎng)勵(lì)

閱讀 641·2021-07-26 23:38
深入解析CSS FlexBox

閱讀 2515·2019-08-30 10:48
淺談 CSS 中的偽類 after

閱讀 1385·2019-08-28 18:07
數(shù)字孿生——思考IoT未來(lái)，UINO2019展會(huì)邀您蒞臨！

閱讀 422·2019-08-26 13:44

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

算法導(dǎo)論筆記動(dòng)態(tài)規(guī)劃DP詳解-鋼條切割的分析與實(shí)現(xiàn)

相關(guān)文章

[Leetcode] Edit Distance 最小編輯距離

**算法動(dòng)態(tài)規(guī)劃的代碼優(yōu)化詳解(經(jīng)典的背包問題)**

**算法動(dòng)態(tài)規(guī)劃的代碼優(yōu)化詳解(經(jīng)典的背包問題)**

發(fā)表評(píng)論

0條評(píng)論

shinezejian

男|高級(jí)講師

TA的文章

#黑五#hostarmada：共享主機(jī)80%折扣，vps主機(jī)30%折扣，新加坡/美國(guó)等9機(jī)房

面試官問我Redis集群，我真的是

C語(yǔ)言進(jìn)階：動(dòng)態(tài)內(nèi)存管理

干貨|app自動(dòng)化測(cè)試之Andriod WebView如何測(cè)試

2020騰訊云產(chǎn)品采購(gòu)季有獎(jiǎng)問卷調(diào)查,認(rèn)真填寫送騰訊云代金券獎(jiǎng)勵(lì)

深入解析CSS FlexBox

淺談 CSS 中的偽類 after

數(shù)字孿生——思考IoT未來(lái)，UINO2019展會(huì)邀您蒞臨！

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

算法導(dǎo)論筆記動(dòng)態(tài)規(guī)劃DP詳解-鋼條切割的分析與實(shí)現(xiàn)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！