C++0-1背包問(wèn)題

背包問(wèn)題是一個(gè)非常好的動(dòng)態(tài)規(guī)劃入門(mén)題目，是動(dòng)態(tài)規(guī)劃中最常見(jiàn)的問(wèn)題形式。其具有很多變種，例如 0-1 背包問(wèn)題、完全背包問(wèn)題、多重背包問(wèn)題等。

在本節(jié)中，我們先來(lái)求解最常見(jiàn)的 0-1 背包問(wèn)題。

觀察圖 14-17 ，由于物品編號(hào) $i$ 從 $1$ 開(kāi)始計(jì)數(shù)，數(shù)組索引從 $0$ 開(kāi)始計(jì)數(shù)，因此物品 $i$ 對(duì)應(yīng)重量 $wgt[i?1]$ 和價(jià)值 $val[i?1]$ 。

圖 14-17   0-1 背包的示例數(shù)據(jù)

我們可以將 0-1 背包問(wèn)題看作是一個(gè)由 $n$ 輪決策組成的過(guò)程，每個(gè)物體都有不放入和放入兩種決策，因此該問(wèn)題是滿(mǎn)足決策樹(shù)模型的。

該問(wèn)題的目標(biāo)是求解“在限定背包容量下的最大價(jià)值”，因此較大概率是個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題。

第一步：思考每輪的決策，定義狀態(tài)，從而得到 $dp$ 表

對(duì)于每個(gè)物品來(lái)說(shuō)，不放入背包，背包容量不變；放入背包，背包容量減小。由此可得狀態(tài)定義：當(dāng)前物品編號(hào) $i$ 和剩余背包容量 $c$ ，記為 $[i,c]$ 。

狀態(tài) $[i,c]$ 對(duì)應(yīng)的子問(wèn)題為：前 $i$ 個(gè)物品在剩余容量為 $c$ 的背包中的最大價(jià)值，記為 $dp[i,c]$ 。

待求解的是 $dp[n,cap]$ ，因此需要一個(gè)尺寸為 $(n+1)\times (cap+1)$ 的二維 $dp$ 表。

第二步：找出最優(yōu)子結(jié)構(gòu)，進(jìn)而推導(dǎo)出狀態(tài)轉(zhuǎn)移方程

當(dāng)我們做出物品 $i$ 的決策后，剩余的是前 $i?1$ 個(gè)物品的決策，可分為以下兩種情況。

• 不放入物品 $i$ ：背包容量不變，狀態(tài)變化為 $[i?1,c]$ 。
• 放入物品 $i$ ：背包容量減小 $wgt[i?1]$ ，價(jià)值增加 $val[i?1]$ ，狀態(tài)變化為 $[i?1,c?wgt[i?1]]$ 。

上述分析向我們揭示了本題的最優(yōu)子結(jié)構(gòu)：最大價(jià)值 $dp[i,c]$ 等于不放入物品 $i$ 和放入物品 $i$ 兩種方案中的價(jià)值更大的那一個(gè)。由此可推出狀態(tài)轉(zhuǎn)移方程：

需要注意的是，若當(dāng)前物品重量 $wgt[i?1]$ 超出剩余背包容量 $c$ ，則只能選擇不放入背包。

第三步：確定邊界條件和狀態(tài)轉(zhuǎn)移順序

當(dāng)無(wú)物品或無(wú)剩余背包容量時(shí)最大價(jià)值為 $0$ ，即首列 $dp[i,0]$ 和首行 $dp[0,c]$ 都等于 $0$ 。

當(dāng)前狀態(tài) $[i,c]$ 從上方的狀態(tài) $[i?1,c]$ 和左上方的狀態(tài) $[i?1,c?wgt[i?1]]$ 轉(zhuǎn)移而來(lái)，因此通過(guò)兩層循環(huán)正序遍歷整個(gè) $dp$ 表即可。

根據(jù)以上分析，我們接下來(lái)按順序?qū)崿F(xiàn)暴力搜索、記憶化搜索、動(dòng)態(tài)規(guī)劃解法。

1.   方法一：暴力搜索

搜索代碼包含以下要素。

• 遞歸參數(shù)：狀態(tài) $[i,c]$ 。
• 返回值：子問(wèn)題的解 $dp[i,c]$ 。
• 終止條件：當(dāng)物品編號(hào)越界 $i=0$ 或背包剩余容量為 $0$ 時(shí)，終止遞歸并返回價(jià)值 $0$ 。
• 剪枝：若當(dāng)前物品重量超出背包剩余容量，則只能不放入背包。

knapsack.cpp

/* 0-1 背包：暴力搜索 */
int knapsackDFS(vector<int> &wgt, vector<int> &val, int i, int c) {
    // 若已選完所有物品或背包無(wú)容量，則返回價(jià)值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若超過(guò)背包容量，則只能不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFS(wgt, val, i - 1, c);
    }
    // 計(jì)算不放入和放入物品 i 的最大價(jià)值
    int no = knapsackDFS(wgt, val, i - 1, c);
    int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 返回兩種方案中價(jià)值更大的那一個(gè)
    return max(no, yes);
}

如圖 14-18 所示，由于每個(gè)物品都會(huì)產(chǎn)生不選和選兩條搜索分支，因此時(shí)間復(fù)雜度為 $O(2^n)$ 。

觀察遞歸樹(shù)，容易發(fā)現(xiàn)其中存在重疊子問(wèn)題，例如 $dp[1,10]$ 等。而當(dāng)物品較多、背包容量較大，尤其是相同重量的物品較多時(shí)，重疊子問(wèn)題的數(shù)量將會(huì)大幅增多。

圖 14-18   0-1 背包的暴力搜索遞歸樹(shù)

2.   方法二：記憶化搜索

為了保證重疊子問(wèn)題只被計(jì)算一次，我們借助記憶列表 mem 來(lái)記錄子問(wèn)題的解，其中 mem[i][c] 對(duì)應(yīng) $dp[i,c]$ 。

引入記憶化之后，時(shí)間復(fù)雜度取決于子問(wèn)題數(shù)量，也就是 $O(n\times cap)$ 。

knapsack.cpp

/* 0-1 背包：記憶化搜索 */
int knapsackDFSMem(vector<int> &wgt, vector<int> &val, vector<vector<int>> &mem, int i, int c) {
    // 若已選完所有物品或背包無(wú)容量，則返回價(jià)值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若已有記錄，則直接返回
    if (mem[i][c] != -1) {
        return mem[i][c];
    }
    // 若超過(guò)背包容量，則只能不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFSMem(wgt, val, mem, i - 1, c);
    }
    // 計(jì)算不放入和放入物品 i 的最大價(jià)值
    int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
    int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 記錄并返回兩種方案中價(jià)值更大的那一個(gè)
    mem[i][c] = max(no, yes);
    return mem[i][c];
}

圖 14-19 展示了在記憶化遞歸中被剪掉的搜索分支。

圖 14-19   0-1 背包的記憶化搜索遞歸樹(shù)

3.   方法三：動(dòng)態(tài)規(guī)劃?

動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上就是在狀態(tài)轉(zhuǎn)移中填充 $dp$ 表的過(guò)程，代碼如下所示。

knapsack.cpp

/* 0-1 背包：動(dòng)態(tài)規(guī)劃 */
int knapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    // 狀態(tài)轉(zhuǎn)移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超過(guò)背包容量，則不選物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不選和選物品 i 這兩種方案的較大值
                dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

如圖 14-20 所示，時(shí)間復(fù)雜度和空間復(fù)雜度都由數(shù)組 dp 大小決定，即 $O(n\times cap)$ 。

圖 14-20   0-1 背包的動(dòng)態(tài)規(guī)劃過(guò)程

4.   空間優(yōu)化

由于每個(gè)狀態(tài)都只與其上一行的狀態(tài)有關(guān)，因此我們可以使用兩個(gè)數(shù)組滾動(dòng)前進(jìn)，將空間復(fù)雜度從 $O(n^2)$ 將低至 $O(n)$ 。

進(jìn)一步思考，我們是否可以?xún)H用一個(gè)數(shù)組實(shí)現(xiàn)空間優(yōu)化呢？觀察可知，每個(gè)狀態(tài)都是由正上方或左上方的格子轉(zhuǎn)移過(guò)來(lái)的。假設(shè)只有一個(gè)數(shù)組，當(dāng)開(kāi)始遍歷第 $i$ 行時(shí)，該數(shù)組存儲(chǔ)的仍然是第 $i?1$ 行的狀態(tài)。

• 如果采取正序遍歷，那么遍歷到 $dp[i,j]$ 時(shí)，左上方 $dp[i?1,1]$ ~ $dp[i?1,j?1]$ 值可能已經(jīng)被覆蓋，此時(shí)就無(wú)法得到正確的狀態(tài)轉(zhuǎn)移結(jié)果。
• 如果采取倒序遍歷，則不會(huì)發(fā)生覆蓋問(wèn)題，狀態(tài)轉(zhuǎn)移可以正確進(jìn)行。

圖 14-21 展示了在單個(gè)數(shù)組下從第 $i=1$ 行轉(zhuǎn)換至第 $i=2$ 行的過(guò)程。請(qǐng)思考正序遍歷和倒序遍歷的區(qū)別。

圖 14-21   0-1 背包的空間優(yōu)化后的動(dòng)態(tài)規(guī)劃過(guò)程

在代碼實(shí)現(xiàn)中，我們僅需將數(shù)組 dp 的第一維 $i$ 直接刪除，并且把內(nèi)循環(huán)更改為倒序遍歷即可。

knapsack.cpp

/* 0-1 背包：空間優(yōu)化后的動(dòng)態(tài)規(guī)劃 */
int knapsackDPComp(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<int> dp(cap + 1, 0);
    // 狀態(tài)轉(zhuǎn)移
    for (int i = 1; i <= n; i++) {
        // 倒序遍歷
        for (int c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不選和選物品 i 這兩種方案的較大值
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}