【動態規劃】背包問題 {01背包問題；完全背包問題；二維費用背包問題}

一、背包問題概述

背包問題(Knapsackproblem)是?種組合優化的NP完全問題。

問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最?。

根據物品的個數，分為如下幾類：

01背包問題：每個物品只有?個
完全背包問題：每個物品有?限多個
多重背包問題：每件物品最多有si個
混合背包問題：每個物品會有上?三種情況…
分組背包問題：物品有n組，每組物品里有若干個，每組里最多選一個物品

其中上述分類里面，根據背包是否裝滿，?分為兩類：

不?定裝滿背包
背包?定裝滿

優化?案：

空間優化-滾動數組
單調隊列優化
貪?優化

根據限定條件的個數，又分為兩類：

限定條件只有?個：比如體積->普通的背包問題
限定條件有兩個：比如體積+重量->?維費?背包問題

根據不同的問法，又分為很多類：

輸出?案
求?案總數
最優?案
?案可?性

其實還有很多分類，但是我們僅需了解即可。
因此，背包問題種類非常繁多，題型非常豐富，難度也是非常難以捉摸。但是，盡管種類非常多，都是從01背包問題演化過來的。所以，?定要把01背包問題學好。

二、相關編程題

2.1 01背包問題

2.1.1 01背包（模板）

題目鏈接

【模板】01背包_牛客題霸_牛客網 (nowcoder.com)

題目描述

在這里插入圖片描述

算法原理

在這里插入圖片描述

編寫代碼

#include <iostream>
#include <cstring>
using namespace std;
#define N 1010int n, V;
int v[N], w[N];
int dp[N][N];int main() {//讀入數據cin >> n >> V;for(int i = 1; i <= n; ++i) //注意所有下標從1開始{cin >> v[i] >> w[i];}//解決第一問for(int i = 1; i <= n; ++i){for(int j = 1; j <= V; ++j){dp[i][j] = dp[i-1][j]; // 不選i物品if(j>=v[i]) //要保證不越界，有空間存放v[i]dp[i][j] = max(dp[i][j], w[i]+dp[i-1][j-v[i]]); //選i物品}}cout << dp[n][V] << endl;//解決第二問memset(dp, 0, sizeof(dp));for(int j = 1; j <= V; ++j) dp[0][j] = -1; //-1表示恰好裝滿體積j無解for(int i = 1; i <= n; ++i){for(int j = 1; j <= V; ++j){dp[i][j] = dp[i-1][j]; // 不選i物品if(j>=v[i] && dp[i-1][j-v[i]]!=-1) //條件1保證不越界，有空間存放v[i]；條件2保證恰好裝滿dp[i][j] = max(dp[i][j], w[i]+dp[i-1][j-v[i]]); //選i物品}}cout << (dp[n][V]==-1? 0:dp[n][V]) << endl;
}//空間優化
int dp[N];int main() {//讀入數據...//解決第一問for(int i = 1; i <= n; ++i){for(int j = V; j>=v[i]; --j) //注意從右往左遍歷dp[j] = max(dp[j], w[i]+dp[j-v[i]]);}cout << dp[V] << endl;//解決第二問memset(dp, 0, sizeof(dp));for(int j = 1; j <= V; ++j) dp[j] = -1; //-1表示恰好裝滿體積j無解for(int i = 1; i <= n; ++i){for(int j = V; j>=v[i]; --j){if(dp[j-v[i]]!=-1)dp[j] = max(dp[j], w[i]+dp[j-v[i]]);}}cout << (dp[V]==-1? 0:dp[V]) << endl;
}

2.1.2 分割等和子集

題目鏈接

416. 分割等和子集 - 力扣（LeetCode）

題目描述

在這里插入圖片描述

算法原理

在這里插入圖片描述

01背包必須裝滿
為什么不用-1標識無解？因為其狀態表示中自帶無解判斷（false）

編寫代碼

//空間優化
class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size();int sum = 0;for(auto e : nums) sum+=e;if(sum%2==1) return false;vector<bool> dp(sum/2+1);dp[0] = true;for(int i = 1; i <= n; ++i){for(int j = sum/2; j >= nums[i-1]; --j)dp[j] = dp[j] || dp[j-nums[i-1]];}return dp[sum/2];}
};

2.1.3 目標和

題目鏈接

494. 目標和 - 力扣（LeetCode）

題目描述

在這里插入圖片描述

算法原理

在這里插入圖片描述

01背包必須裝滿
為什么不用-1標識無解？因為其狀態表示中自帶無解判斷（0種選法）

編寫代碼

//空間優化
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int n = nums.size();int sum = 0;for(auto e : nums) sum+=e;int a = (sum+target)/2;if(a<0 || (sum+target)%2==1) return false; //a是所有正數的和；必須是偶數能被2整除；vector<int> dp(a+1);dp[0] = 1;for(int i = 1; i <= n; ++i){for(int j = a; j >= nums[i-1]; --j)dp[j] += dp[j-nums[i-1]];}return dp[a];}
};

2.1.4 最后一塊石頭的重量Ⅱ

題目鏈接

1049. 最后一塊石頭的重量 II - 力扣（LeetCode）

題目描述

在這里插入圖片描述

算法原理

在這里插入圖片描述

01背包不必裝滿

編寫代碼

//空間優化
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size();int sum = 0;for(auto e : stones) sum+=e;int aim = sum/2;vector<int> dp(aim+1);for(int i = 1; i <= n; ++i){for(int j = aim; j >=stones[i-1]; --j)dp[j] = max(dp[j], stones[i-1]+dp[j-stones[i-1]]);}return sum-dp[aim]*2;}
};

2.2 完全背包問題

2.2.1 完全背包（模板）

題目鏈接

【模板】完全背包_牛客題霸_牛客網 (nowcoder.com)

題目描述

在這里插入圖片描述

算法原理

在這里插入圖片描述

和01背包唯一的不同點就是每個物品可以選擇無數次，因此在選擇i物品的狀態轉移方程中有所變化。

提示：綜合了01背包、通配符匹配、正則表達式匹配的考點

編寫代碼

#include <iostream>
#include <cstring>
using namespace std;const int N = 1010;
int n, V;
int v[N], w[N];
int dp[N][N];int main() {//讀入數據cin >> n >> V;for(int i = 1; i <= n; ++i)cin >> v[i] >> w[i];//解決第一問for(int i = 1; i <= n; ++i){for(int j = 1; j <= V; ++j){dp[i][j] = dp[i-1][j];if(j >= v[i])dp[i][j] = max(dp[i][j], dp[i][j-v[i]]+w[i]);}}cout << dp[n][V] << endl;//解決第二問memset(dp, 0, sizeof(dp));for(int j = 1; j <= V; ++j) dp[0][j] = -1;for(int i = 1; i <= n; ++i){for(int j = 1; j <= V; ++j){dp[i][j] = dp[i-1][j];if(j >= v[i] && dp[i][j-v[i]]!=-1)dp[i][j] = max(dp[i][j], dp[i][j-v[i]]+w[i]);}}cout << (dp[n][V]==-1? 0:dp[n][V]) << endl;
}//空間優化
int dp[N];int main() {//讀入數據...//解決第一問for(int i = 1; i <= n; ++i){for(int j = v[i]; j <= V; ++j) //注意從左往右遍歷{dp[j] = max(dp[j], dp[j-v[i]]+w[i]);}}cout << dp[V] << endl;//解決第二問memset(dp, 0, sizeof(dp));for(int j = 1; j <= V; ++j) dp[j] = -1;for(int i = 1; i <= n; ++i){for(int j = v[i]; j <= V; ++j){if(dp[j-v[i]]!=-1)dp[j] = max(dp[j], dp[j-v[i]]+w[i]);}}cout << (dp[V]==-1? 0:dp[V]) << endl;
}

2.2.2 零錢兌換

題目鏈接

322. 零錢兌換 - 力扣（LeetCode）

題目描述

在這里插入圖片描述

算法原理

在這里插入圖片描述

提示：不能再像完全背包那樣用-1表示無解。因為這里求的是最小值，如果使用-1，而不選i位置無解，即使選擇i位置的零錢有解，也會在取min時取到-1。實際上我們設置無解為-1的初衷就是為了不參與后續的比較，因此可以用INF（無窮大）表示無解，這樣的話，在取min時永遠不會取到INF。

編寫代碼

class Solution {
public:int coinChange(vector<int>& coins, int amount) {const int INF = 0x3f3f3f3f;int n = coins.size();vector<vector<int>> dp(n+1, vector<int>(amount+1));for(int j = 1; j <= amount; ++j) dp[0][j] = INF;for(int i = 1; i <= n; ++i){for(int j = 1; j <= amount; ++j){dp[i][j] = dp[i-1][j];if(j >= coins[i-1])dp[i][j] = min(dp[i][j], dp[i][j-coins[i-1]]+1);}}return dp[n][amount]>=INF? -1:dp[n][amount];}
};//空間優化
class Solution {
public:int coinChange(vector<int>& coins, int amount) {const int INF = 0x3f3f3f3f;int n = coins.size();vector<int> dp(amount+1);for(int j = 1; j <= amount; ++j) dp[j] = INF;for(int i = 1; i <= n; ++i){for(int j = coins[i-1]; j <= amount; ++j)dp[j] = min(dp[j], dp[j-coins[i-1]]+1);}return dp[amount]>=INF? -1:dp[amount];}
};

2.2.3 零錢兌換Ⅱ

題目鏈接

518. 零錢兌換 II - 力扣（LeetCode）

題目描述

在這里插入圖片描述

算法原理

在這里插入圖片描述

編寫代碼

class Solution {
public:int change(int amount, vector<int>& coins) {int n = coins.size();vector<int> dp(amount+1);dp[0] = 1;for(auto e : coins){for(int j = e; j <= amount; ++j)dp[j]+=dp[j-e];  }return dp[amount];}
};

2.2.4 完全平方數

題目鏈接

279. 完全平方數 - 力扣（LeetCode）

題目描述

在這里插入圖片描述

算法原理

在這里插入圖片描述

編寫代碼

class Solution {
public:int numSquares(int n) {int m = sqrt(n);const int INF = 0x3f3f3f3f;vector<int> dp(n+1, INF);dp[0] = 0;for(int i = 1; i <= m; ++i){for(int j = i*i; j <= n; ++j)dp[j] = min(dp[j], dp[j-i*i]+1);}return dp[n];}
};

2.3 二維費用背包問題

2.3.1 一和零

題目鏈接

474. 一和零 - 力扣（LeetCode）

題目描述

在這里插入圖片描述

算法原理

在這里插入圖片描述

01背包，不必裝滿，二維費用

編寫代碼

//三維dp表
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int cnt = strs.size();vector<vector<vector<int>>> dp(cnt+1, vector<vector<int>>(m+1, vector<int>(n+1)));for(int i = 1; i <= cnt; ++i){//統計以下字符串中0，1的個數int c0 = Count0(strs[i-1]);int c1 = strs[i-1].size()-c0;for(int j = 0; j <= m; ++j)for(int k = 0; k <= n; ++k){dp[i][j][k] = dp[i-1][j][k]; //不選i位置的字符串if(j>=c0 && k>=c1) //選i位置的字符串dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-c0][k-c1]+1);}}return dp[cnt][m][n];}int Count0(const string& str){int cnt = 0;for(auto ch : str)if(ch == '0') ++cnt;return cnt;}
};//空間優化：二維dp表
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int cnt = strs.size();vector<vector<int>> dp(m+1, vector<int>(n+1));for(int i = 1; i <= cnt; ++i){int c0 = Count0(strs[i-1]);int c1 = strs[i-1].size()-c0;for(int j = m; j >= c0; --j) //注意從大到小遍歷for(int k = n; k >= c1; --k){dp[j][k] = max(dp[j][k], dp[j-c0][k-c1]+1);}}return dp[m][n];}
};

2.3.2 盈利計劃

題目鏈接

879. 盈利計劃 - 力扣（LeetCode）

題目描述

在這里插入圖片描述

算法原理

在這里插入圖片描述

提示：k可以小于p[i]，表示單單i項計劃的盈利就超過了最低限度k。但是作為數組的下標k-p[i]不能是負數，因此我們采取一個折中的方案，當k-p[i]<0時從前i-1項計劃中選擇的總利潤最低為0即可。

編寫代碼

//三維dp表
class Solution {
public:int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit) {int cnt = group.size();vector<vector<vector<int>>> dp(cnt+1, vector<vector<int>>(n+1, vector<int>(m+1)));for(int j = 0; j <= n; ++j) dp[0][j][0] = 1; //沒有計劃，沒有利潤，無論多少人數都可以選空for(int i = 1; i <= cnt; ++i){for(int j = 0; j <= n; ++j){for(int k = 0; k <= m; ++k){dp[i][j][k] = dp[i-1][j][k];if(j>=group[i-1])dp[i][j][k] += dp[i-1][j-group[i-1]][max(0, k-profit[i-1])];dp[i][j][k] %= (int)1e9+7;}}}return dp[cnt][n][m];}
};//空間優化：二維dp表
class Solution {
public:int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit) {int cnt = group.size();vector<vector<int>> dp(n+1, vector<int>(m+1));for(int j = 0; j <= n; ++j) dp[j][0] = 1;for(int i = 1; i <= cnt; ++i){for(int j = n; j >= group[i-1]; --j)for(int k = m; k >= 0; --k){dp[j][k] += dp[j-group[i-1]][max(0, k-profit[i-1])];dp[j][k] %= (int)1e9+7;}}return dp[n][m];}
};