技術(shù)交流QQ群:1027579432口四，歡迎你的加入窃植！
歡迎關(guān)注我的微信公眾號：CurryCoder的程序人生
1. 01背包問題
-
01背包的算法思想
01背包.jpg - 01背包的代碼框架
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; const int N = 1010; int n, m; // n表示所有物品的個數(shù) m表示背包的容量 int v[N], w[N]; // v表示第i件物品的體積 w表示第i件物品的價值 int f[N][N]; // 所有狀態(tài) int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) cin >> v[i] >> w[i]; // f[0][0~m] = 0 for(int i = 1; i <= n; i++){ // 枚舉所有的物品 for(int j = 0; j <= m; j++){ // 枚舉所有的體積 f[i][j] = f[i-1][j]; if(j >= v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]); // 注意此處的判斷 } } cout << f[n][m] << endl; return 0; } - 優(yōu)化方法---優(yōu)化成一維數(shù)組來表述集合
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; const int N = 1010; int n, m; // n表示所有物品的個數(shù) m表示背包的容量 int v[N], w[N]; // v表示第i件物品的體積 w表示第i件物品的價值 int f[N]; // 所有狀態(tài) int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i++){ // 枚舉所有的物品 for(int j = m; j >= v[i]; j--){ // 枚舉所有的體積 f[j] = max(f[j], f[j-v[i]] + w[i]); // 注意此處的判斷 } } cout << f[m] << endl; return 0; }
2. 完全背包問題
-
完全背包的算法思想
完全背包.jpg - 完全背包的代碼框架---樸素方法
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; const int N = 1010; int n, m; // n表示所有物品的個數(shù) m表示背包的容量 int v[N], w[N]; // v表示第i件物品的體積 w表示第i件物品的價值 int f[N][N]; // 所有狀態(tài) int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i++){ for(int j = 0; j <= m; j++){ for(int k = 0; k * v[i] <= j; k++){ f[i][j] = max(f[i][j], f[i-1][j - v[i] * k] + k * w[i]); } } } cout << f[n][m] << endl; return 0; } - 優(yōu)化方法
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; const int N = 1010; int n, m; // n表示所有物品的個數(shù) m表示背包的容量 int v[N], w[N]; // v表示第i件物品的體積 w表示第i件物品的價值 int f[N][N]; // 所有狀態(tài) int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i++){ for(int j = 0; j <= m; j++){ f[i][j] = f[i-1][j]; if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]); } } cout << f[n][m] << endl; return 0; }
3.多重背包問題
-
多重背包的算法思想
多重背包.jpg - 多重背包的算法框架---樸素方法
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; const int N = 110; int n, m; // n表示所有物品的個數(shù) m表示背包的容量 int v[N], w[N], s[N]; // v表示第i件物品的體積 w表示第i件物品的價值,s[i]表示每件物品最多有s[i]個 int f[N][N]; // 所有狀態(tài) int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i]; for(int i = 1; i <= n; i++) // 枚舉所有物品 for(int j = 0; j <= m; j++) // 枚舉所有體積 for(int k = 0; k <= s[i] && k * v[i] <= j; k++) // k：表示每件物品的個數(shù)最多有s[i]個 f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k); cout << f[n][m] << endl; return 0; } - 優(yōu)化方法--二進制優(yōu)化方法
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; const int N = 25000, M = 2010; int n, m; // n表示所有物品的個數(shù) m表示背包的容量 int v[N], w[N], s[N]; // v表示第i件物品的體積 w表示第i件物品的價值,s[i]表示每件物品最多有s[i]個 int f[N]; // 所有狀態(tài) int main(){ cin >> n >> m; int cnt = 0; for(int i = 1; i <= n; i++) { int a, b, s; // 體積 價值 個數(shù) cin >> a >> b >> s; int k = 1; // 多重背包的二進制優(yōu)化方法 while(k <= s){ cnt++; v[cnt] = a * k; w[cnt] = b * k; s -= k; k *= 2; } // s[i]中的剩余部分 if(s > 0){ cnt++; v[cnt] = a * s; w[cnt] = b * s; } } // 優(yōu)化版本的01背包問題 n = cnt; for(int i = 1; i <= n; i++){ for(int j = m; j >= v[i]; j--){ f[j] = max(f[j], f[j - v[i]] + w[i]); } } cout << f[m] << endl; return 0; }
4.分組背包問題
-
分組背包的算法思想
分組背包.jpg - 分組背包的算法框架---優(yōu)化方法
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; const int N = 110; int n, m; // n表示所有物品的個數(shù) m表示背包的容量 int v[N][N], w[N][N], s[N]; // v表示第i件物品的體積 w表示第i件物品的價值, S[i]:每組中物品的個數(shù) int f[N]; // 從兩維優(yōu)化成一維 int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> s[i]; for(int j = 0; j < s[i]; j++) cin >> v[i][j] >> w[i][j]; } for(int i = 1; i <= n; i++) // 枚舉每一組 for(int j = m; j >= 0; j--) // 改成一維表示狀態(tài)時，從大到小來枚舉所有體積！ for(int k = 0; k < s[i]; k++) // 枚舉每組中每一個物品 if(v[i][k] <= j) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]); // v[i][k]:第i組中的第k個物品 cout << f[m] << endl; return 0; }
