閱讀(1.4k) 書簽贊(0) 我要糾錯

C++完全背包問題

2023-09-20 15:41 更新

在本節(jié)中，我們先求解另一個常見的背包問題：完全背包，再了解它的一種特例：零錢兌換。

完全背包

Question

給定 $n$ 個物品，第 $i$ 個物品的重量為 $w g t [i ? 1]$ 、價值為 $v a l [i ? 1]$ ，和一個容量為 $c a p$ 的背包。每個物品可以重復(fù)選取，問在不超過背包容量下能放入物品的最大價值。

完全背包問題的示例數(shù)據(jù)

圖 14-22 完全背包問題的示例數(shù)據(jù)

1. 動態(tài)規(guī)劃思路

完全背包和 0-1 背包問題非常相似，區(qū)別僅在于不限制物品的選擇次數(shù)。

在 0-1 背包中，每個物品只有一個，因此將物品 $i$ 放入背包后，只能從前 $i ? 1$ 個物品中選擇。
在完全背包中，每個物品有無數(shù)個，因此將物品 $i$ 放入背包后，仍可以從前 $i$ 個物品中選擇。

在完全背包的規(guī)定下，狀態(tài) $[i, c]$ 的變化分為兩種情況。

不放入物品 $i$ ：與 0-1 背包相同，轉(zhuǎn)移至 $[i ? 1, c]$ 。
放入物品 $i$ ：與 0-1 背包不同，轉(zhuǎn)移至 $[i, c ? w g t [i ? 1]]$ 。

從而狀態(tài)轉(zhuǎn)移方程變?yōu)椋?/p>

d p [i, c] = max (d p [i ? 1, c], d p [i, c ? w g t [i ? 1]] + v a l [i ? 1])

2. 代碼實現(xiàn)

對比兩道題目的代碼，狀態(tài)轉(zhuǎn)移中有一處從 $i ? 1$ 變?yōu)? $i$ ，其余完全一致。

unbounded_knapsack.cpp

/* 完全背包：動態(tài)規(guī)劃 */
int unboundedKnapsackDP(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) {
                // 若超過背包容量，則不選物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不選和選物品 i 這兩種方案的較大值
                dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

3. 空間優(yōu)化

由于當前狀態(tài)是從左邊和上邊的狀態(tài)轉(zhuǎn)移而來，因此空間優(yōu)化后應(yīng)該對 $d p$ 表中的每一行采取正序遍歷。

這個遍歷順序與 0-1 背包正好相反。請借助圖 14-23 來理解兩者的區(qū)別。

unbounded_knapsack_dp_comp_step2

unbounded_knapsack_dp_comp_step3

圖 14-23 完全背包的空間優(yōu)化后的動態(tài)規(guī)劃過程

代碼實現(xiàn)比較簡單，僅需將數(shù)組 dp 的第一維刪除。

unbounded_knapsack.cpp

/* 完全背包：空間優(yōu)化后的動態(tài)規(guī)劃 */
int unboundedKnapsackDPComp(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 = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超過背包容量，則不選物品 i
                dp[c] = dp[c];
            } else {
                // 不選和選物品 i 這兩種方案的較大值
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}

零錢兌換問題

背包問題是一大類動態(tài)規(guī)劃問題的代表，其擁有很多的變種，例如零錢兌換問題。

Question

給定 $n$ 種硬幣，第 $i$ 種硬幣的面值為 $c o i n s [i ? 1]$ ，目標金額為 $a m t$ ，每種硬幣可以重復(fù)選取，問能夠湊出目標金額的最少硬幣個數(shù)。如果無法湊出目標金額則返回 $? 1$ 。

零錢兌換問題的示例數(shù)據(jù)

圖 14-24 零錢兌換問題的示例數(shù)據(jù)

1. 動態(tài)規(guī)劃思路

零錢兌換可以看作是完全背包的一種特殊情況，兩者具有以下聯(lián)系與不同點。

兩道題可以相互轉(zhuǎn)換，“物品”對應(yīng)于“硬幣”、“物品重量”對應(yīng)于“硬幣面值”、“背包容量”對應(yīng)于“目標金額”。
優(yōu)化目標相反，背包問題是要最大化物品價值，零錢兌換問題是要最小化硬幣數(shù)量。
背包問題是求“不超過”背包容量下的解，零錢兌換是求“恰好”湊到目標金額的解。

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

狀態(tài) $[i, a]$ 對應(yīng)的子問題為：前 $i$ 種硬幣能夠湊出金額 $a$ 的最少硬幣個數(shù)，記為 $d p [i, a]$ 。

二維 $d p$ 表的尺寸為 $(n + 1) \times (a m t + 1)$ 。

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

本題與完全背包的狀態(tài)轉(zhuǎn)移方程存在以下兩個差異。

本題要求最小值，因此需將運算符 $max ()$ 更改為 $min ()$ 。
優(yōu)化主體是硬幣數(shù)量而非商品價值，因此在選中硬幣時執(zhí)行 $+ 1$ 即可。

d p [i, a] = min (d p [i ? 1, a], d p [i, a ? c o i n s [i ? 1]] + 1)

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

當目標金額為 $0$ 時，湊出它的最少硬幣個數(shù)為 $0$ ，即首列所有 $d p [i, 0]$ 都等于 $0$ 。

當無硬幣時，無法湊出任意 $> 0$ 的目標金額，即是無效解。為使狀態(tài)轉(zhuǎn)移方程中的 $min ()$ 函數(shù)能夠識別并過濾無效解，我們考慮使用 $+ \infty$ 來表示它們，即令首行所有 $d p [0, a]$ 都等于 $+ \infty$ 。

2. 代碼實現(xiàn)

大多數(shù)編程語言并未提供 $+ \infty$ 變量，只能使用整型 int 的最大值來代替。而這又會導(dǎo)致大數(shù)越界：狀態(tài)轉(zhuǎn)移方程中的 $+ 1$ 操作可能發(fā)生溢出。

為此，我們采用數(shù)字 $a m t + 1$ 來表示無效解，因為湊出 $a m t$ 的硬幣個數(shù)最多為 $a m t$ 個。

最后返回前，判斷 $d p [n, a m t]$ 是否等于 $a m t + 1$ ，若是則返回 $? 1$ ，代表無法湊出目標金額。

coin_change.cpp

/* 零錢兌換：動態(tài)規(guī)劃 */
int coinChangeDP(vector<int> &coins, int amt) {
    int n = coins.size();
    int MAX = amt + 1;
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
    // 狀態(tài)轉(zhuǎn)移：首行首列
    for (int a = 1; a <= amt; a++) {
        dp[0][a] = MAX;
    }
    // 狀態(tài)轉(zhuǎn)移：其余行列
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超過背包容量，則不選硬幣 i
                dp[i][a] = dp[i - 1][a];
            } else {
                // 不選和選硬幣 i 這兩種方案的較小值
                dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
            }
        }
    }
    return dp[n][amt] != MAX ? dp[n][amt] : -1;
}

圖 14-25 展示了零錢兌換的動態(tài)規(guī)劃過程，和完全背包非常相似。

零錢兌換問題的動態(tài)規(guī)劃過程

coin_change_dp_step2 coin_change_dp_step3 coin_change_dp_step4 coin_change_dp_step5 coin_change_dp_step6 coin_change_dp_step7 coin_change_dp_step8 coin_change_dp_step9 coin_change_dp_step10 coin_change_dp_step11 coin_change_dp_step12 coin_change_dp_step13 coin_change_dp_step14 coin_change_dp_step15

圖 14-25 零錢兌換問題的動態(tài)規(guī)劃過程

3. 空間優(yōu)化

零錢兌換的空間優(yōu)化的處理方式和完全背包一致。

coin_change.cpp

/* 零錢兌換：空間優(yōu)化后的動態(tài)規(guī)劃 */
int coinChangeDPComp(vector<int> &coins, int amt) {
    int n = coins.size();
    int MAX = amt + 1;
    // 初始化 dp 表
    vector<int> dp(amt + 1, MAX);
    dp[0] = 0;
    // 狀態(tài)轉(zhuǎn)移
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超過背包容量，則不選硬幣 i
                dp[a] = dp[a];
            } else {
                // 不選和選硬幣 i 這兩種方案的較小值
                dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
            }
        }
    }
    return dp[amt] != MAX ? dp[amt] : -1;
}

零錢兌換問題 II

Question

給定 $n$ 種硬幣，第 $i$ 種硬幣的面值為 $c o i n s [i ? 1]$ ，目標金額為 $a m t$ ，每種硬幣可以重復(fù)選取，問在湊出目標金額的硬幣組合數(shù)量。

零錢兌換問題 II 的示例數(shù)據(jù)

圖 14-26 零錢兌換問題 II 的示例數(shù)據(jù)

1. 動態(tài)規(guī)劃思路

相比于上一題，本題目標是組合數(shù)量，因此子問題變?yōu)椋?strong>前 $i$ 種硬幣能夠湊出金額 $a$ 的組合數(shù)量。而 $d p$ 表仍然是尺寸為 $(n + 1) \times (a m t + 1)$ 的二維矩陣。

當前狀態(tài)的組合數(shù)量等于不選當前硬幣與選當前硬幣這兩種決策的組合數(shù)量之和。狀態(tài)轉(zhuǎn)移方程為：

d p [i, a] = d p [i ? 1, a] + d p [i, a ? c o i n s [i ? 1]]

當目標金額為 $0$ 時，無須選擇任何硬幣即可湊出目標金額，因此應(yīng)將首列所有 $d p [i, 0]$ 都初始化為 $1$ 。當無硬幣時，無法湊出任何 $> 0$ 的目標金額，因此首行所有 $d p [0, a]$ 都等于 $0$ 。

2. 代碼實現(xiàn)

coin_change_ii.cpp

/* 零錢兌換 II：動態(tài)規(guī)劃 */
int coinChangeIIDP(vector<int> &coins, int amt) {
    int n = coins.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
    // 初始化首列
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    // 狀態(tài)轉(zhuǎn)移
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超過背包容量，則不選硬幣 i
                dp[i][a] = dp[i - 1][a];
            } else {
                // 不選和選硬幣 i 這兩種方案之和
                dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
            }
        }
    }
    return dp[n][amt];
}

3. 空間優(yōu)化

空間優(yōu)化處理方式相同，刪除硬幣維度即可。

coin_change_ii.cpp

/* 零錢兌換 II：空間優(yōu)化后的動態(tài)規(guī)劃 */
int coinChangeIIDPComp(vector<int> &coins, int amt) {
    int n = coins.size();
    // 初始化 dp 表
    vector<int> dp(amt + 1, 0);
    dp[0] = 1;
    // 狀態(tài)轉(zhuǎn)移
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超過背包容量，則不選硬幣 i
                dp[a] = dp[a];
            } else {
                // 不選和選硬幣 i 這兩種方案之和
                dp[a] = dp[a] + dp[a - coins[i - 1]];
            }
        }
    }
    return dp[amt];
}

以上內(nèi)容是否對您有幫助：

← C++0-1背包問題

C++編輯距離問題 →

寫筆記

我要補充