問(wèn)題描述：

0-1背包問(wèn)題：給定n種物品和一背包。物品 i 的重量似乎 wi，其價(jià)值為 vi，背包的容量為 c。問(wèn)應(yīng)該如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大？

說(shuō)實(shí)在的，書(shū)上講的東西生澀難懂，我更偏向于看一些有趣的東西。我們來(lái)?yè)Q一個(gè)風(fēng)格來(lái)描述這一個(gè)問(wèn)題。
以下內(nèi)容大部分來(lái)自《算法圖解》一書(shū)。看完之后大有收獲。

另一種風(fēng)格的描述：

假設(shè)你是一個(gè)小偷，背著一個(gè)可裝下4磅東西的背包，你可以偷竊的物品如下：

為了讓偷竊的商品價(jià)值最高，你該選擇哪些商品？

簡(jiǎn)單算法

最簡(jiǎn)單的算法是：嘗試各種可能的商品組合，并找出價(jià)值最高的組合。

這樣顯然是可行的，但是速度非常慢。在只有3件商品的情況下，你需要計(jì)算8個(gè)不同的集合；當(dāng)有4件商品的時(shí)候，你需要計(jì)算16個(gè)不同的集合。每增加一件商品，需要計(jì)算的集合數(shù)都將翻倍！這種算法的運(yùn)行時(shí)間是O(2?)，真的是慢如蝸牛。

動(dòng)態(tài)規(guī)劃

解決這樣問(wèn)題的答案就是使用動(dòng)態(tài)規(guī)劃！下面來(lái)看看動(dòng)態(tài)規(guī)劃的工作原理。動(dòng)態(tài)規(guī)劃先解決子問(wèn)題，再逐步解決大問(wèn)題。

對(duì)于背包問(wèn)題，你先解決小背包（子背包）問(wèn)題，再逐步解決原來(lái)的問(wèn)題。

比較有趣的一句話是：每個(gè)動(dòng)態(tài)規(guī)劃都從一個(gè)網(wǎng)格開(kāi)始。

背包問(wèn)題的網(wǎng)格如下：

網(wǎng)格的各行為商品，各列為不同容量（1~4磅）的背包。所有這些列你都需要，因?yàn)樗鼈儗椭阌?jì)算子背包的價(jià)值。

網(wǎng)格最初是空的。你將填充其中的每個(gè)單元格，網(wǎng)格填滿后，就找到了問(wèn)題的答案！

1.吉他行

后面會(huì)列出計(jì)算這個(gè)網(wǎng)格中單元格值得公式，但現(xiàn)在我們先來(lái)一步一步做。首先來(lái)看第一行。

這是吉他行，意味著你將嘗試將吉他裝入背包。在每個(gè)單元格，都需要做一個(gè)簡(jiǎn)單的決定：偷不偷吉他？別忘了，你要找出一個(gè)價(jià)值最高的商品集合。

第一個(gè)單元格表示背包的的容量為1磅。吉他的重量也是1磅，這意味著它能裝入背包！因此這個(gè)單元格包含吉他，價(jià)值為1500美元。

下面來(lái)填充網(wǎng)格。

與這個(gè)單元格一樣，每個(gè)單元格都將包含當(dāng)前可裝入背包的所有商品。

來(lái)看下一個(gè)單元格。這個(gè)單元格表示背包容量為2磅，完全能夠裝下吉他！

這行的其他單元格也一樣。別忘了，這是第一行，只有吉他可供你選擇，換而言之，你假裝現(xiàn)在還沒(méi)發(fā)偷竊其他兩件商品。

此時(shí)你很可能心存疑惑：原來(lái)的問(wèn)題說(shuō)的額是4磅的背包，我們?yōu)楹我紤]容量為1磅、2磅等得背包呢？前面說(shuō)過(guò)，動(dòng)態(tài)規(guī)劃從小問(wèn)題著手，逐步解決大問(wèn)題。這里解決的子問(wèn)題將幫助你解決大問(wèn)題。

別忘了，你要做的是讓背包中商品的價(jià)值最大。這行表示的是當(dāng)前的最大價(jià)值。它指出，如果你有一個(gè)容量4磅的背包，可在其中裝入的商品的最大價(jià)值為1500美元。

你知道這不是最終解。隨著算法往下執(zhí)行，你將逐步修改最大價(jià)值。

2.音響行

我們來(lái)填充下一行——音響行。你現(xiàn)在處于第二行，可以偷竊的商品有吉他和音響。

我們先來(lái)看第一個(gè)單元格，它表示容量為1磅的背包。在此之前，可裝入1磅背包的商品最大價(jià)值為1500美元。

該不該偷音響呢？

背包的容量為1磅，顯然不能裝下音響。由于容量為1磅的背包裝不下音響，因此最大價(jià)值依然是1500美元。

接下來(lái)的兩個(gè)單元格的情況與此相同。在這些單元格中，背包的容量分別為2磅和3磅，而以前的最大價(jià)值為1500美元。由于這些背包裝不下音響，因此最大的價(jià)值保持不變。

背包容量為4磅呢？終于能夠裝下音響了！原來(lái)最大價(jià)值為1500美元，但如果在背包中裝入音響而不是吉他，價(jià)值將為3000美元！因此還是偷音響吧。

你更新了最大價(jià)值。如果背包的容量為4磅，就能裝入價(jià)值至少3000美元的商品。在這個(gè)網(wǎng)格中，你逐步地更新最大價(jià)值。

3.筆記本電腦行

下面以同樣的方式處理筆記本電腦。筆記本電腦重3磅，沒(méi)法將其裝入1磅或者2磅的背包，因此前兩個(gè)單元格的最大價(jià)值仍然是1500美元。

對(duì)于容量為3磅的背包，原來(lái)的最大價(jià)值為1500美元，但現(xiàn)在你可以選擇偷竊價(jià)值2000美元的筆記本電腦而不是吉他，這樣新的最大價(jià)值將為2000美元。

對(duì)于容量為4磅的背包，情況很有趣。這是非常重要的部分。當(dāng)前的最大價(jià)值為3000美元，你可不偷音響，而偷筆記本電腦，但它只值2000美元。

價(jià)值沒(méi)有原來(lái)高，但是等一等，筆記本電腦的重量只有3磅，背包還有1磅的重量沒(méi)用！

在1磅的容量中，可裝入的商品的最大價(jià)值是多少呢？你之前計(jì)算過(guò)。

根據(jù)之前計(jì)算的最大價(jià)值可知，在1磅的容量中可裝入吉他，價(jià)值1500美元。因此，你需要做如下的比較：

你可能始終心存疑惑：為何計(jì)算小背包可裝入的商品的最大價(jià)值呢？但愿你現(xiàn)在明白了其中的原因！余下了空間時(shí)，你可根據(jù)這些子問(wèn)題的答案來(lái)確定余下的空間可裝入哪些商品。筆記本電腦和吉他的總價(jià)值為3500美元，因此偷它們是更好的選擇。

最終的網(wǎng)格類似于下面這樣。

答案如下：將吉他和筆記本電腦裝入背包時(shí)價(jià)值更高，為3500美元。

你可能認(rèn)為，計(jì)算最后一個(gè)單元格的價(jià)值時(shí)，我使用了不同的公式。那是因?yàn)樘畛渲暗膯卧駮r(shí)，我故意避開(kāi)了一些復(fù)雜的因素。其實(shí)，計(jì)算每個(gè)單元格的價(jià)值時(shí)，使用的公式都相同。這個(gè)公式如下。

你可以使用這個(gè)公式來(lái)計(jì)算每個(gè)單元格的價(jià)值，最終的網(wǎng)格將與前一個(gè)網(wǎng)格相同?，F(xiàn)在你明白了為何要求解子問(wèn)題了吧？你可以合并兩個(gè)子問(wèn)題的解來(lái)得到更大問(wèn)題的解。

代碼實(shí)現(xiàn)：

算法的核心是思想，當(dāng)清楚了整個(gè)過(guò)程，那么寫(xiě)代碼就簡(jiǎn)單了，直接來(lái)模擬上述的一個(gè)過(guò)程：

/**
 * @author:我沒(méi)有三顆心臟
 * @create:2017-11-14-10:24
 */
public class MaxBag {
    static int n;           // 描述物品個(gè)數(shù)
    static int c;           // 描述背包容量
    static int[] value;     // 描述物品價(jià)值
    static int[] weight;    // 描述物品重量

    public static void main(String[] args) {
        // 初始賦值操作
        value = new int[]{1500, 3000, 2000};
        weight = new int[]{1, 4, 3};
        c = 4;
        n = 3;

        // 構(gòu)造最優(yōu)解的網(wǎng)格:3行4列
        int[][] maxValue = new int[n][c];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < c; j++) {
                maxValue[i][j] = 0;
            }
        }   // end for

        // 填充網(wǎng)格
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= c; j++) {
                if (i == 0) {
                    maxValue[i][j - 1] = (weight[i] <= j ? value[i] : 0);
                } else {
                    int topValue = maxValue[i - 1][j - 1];  // 上一個(gè)網(wǎng)格的值
                    int thisValue = (weight[i] <= j ?       // 當(dāng)前商品的價(jià)值 + 剩余空間的價(jià)值
                            (j - weight[i] > 0 ? value[i] + maxValue[i - 1][j - weight[i]] : value[i])
                            : topValue);

                    // 返回 topValue和thisValue中較大的一個(gè)
                    maxValue[i][j - 1] = (topValue > thisValue ? topValue : thisValue);
                }   // end if
            }   // end inner for
        }   // end outer for

        // 打印結(jié)果二維數(shù)組maxValue
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < c; j++) {
                System.out.printf("%6d", maxValue[i][j]);
            }
            System.out.println();
        }
    }
}

最后打印出來(lái)的結(jié)果如下：

再增加一件商品將如何呢

假設(shè)你發(fā)現(xiàn)還有第四件商品可偷——一個(gè)iPhone！（或許你會(huì)毫不猶豫的拿走，但是請(qǐng)別忘了問(wèn)題的本身是要拿走價(jià)值最大的商品）

此時(shí)需要重新執(zhí)行前面所做的計(jì)算嗎？不需要。別忘了，動(dòng)態(tài)規(guī)劃逐步計(jì)算最大價(jià)值。到目前為止，計(jì)算出的最大價(jià)值如下：

這意味著背包容量為4磅時(shí)，你最多可偷價(jià)值3500美元的商品。但這是以前的情況，下面再添加表示iPhone的行。

我們還是從第一個(gè)單元格開(kāi)始。iPhone可裝入容量為1磅的背包。之前的最大價(jià)值為1500美元，但iPhone價(jià)值2000美元，因此該偷iPhone而不是吉他。

在下一個(gè)單元格中，你可裝入iPhone和吉他。

對(duì)于第三個(gè)單元格，也沒(méi)有比裝入iPhone和吉他更好的選擇了。

對(duì)于最后一個(gè)單元格，情況比較有趣。當(dāng)前的最大價(jià)值為3500美元，但你可以偷iPhone，這將余下3磅的容量。

3磅容量的最大價(jià)值為2000美元！再加上iPhone價(jià)值2000美元，總價(jià)值為4000美元。新的最大價(jià)值誕生了！

最終的網(wǎng)格如下。

問(wèn)題：沿著一列往下走，最大價(jià)值可能降低嗎？

答案是：不可能。因?yàn)槊看蔚鷷r(shí)，你都存儲(chǔ)的是當(dāng)前的最大價(jià)值。最大價(jià)值不可能比以前低！

總結(jié)：

有時(shí)候教科書(shū)生澀難懂，你需要找一些更好的資料來(lái)幫助你學(xué)習(xí)，更重要的一點(diǎn)是，保持一顆好奇心還有求知欲。

歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)注明出處！
簡(jiǎn)書(shū)ID：@我沒(méi)有三顆心臟
github：wmyskxz
歡迎關(guān)注公眾微信號(hào)：wmyskxz_javaweb
分享自己的Java Web學(xué)習(xí)之路以及各種Java學(xué)習(xí)資料