技术交流QQ群:1027579432，欢迎你的加入！
欢迎关注我的微信公众号：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表示所有物品的个数 m表示背包的容量 int v[N], w[N]; // v表示第i件物品的体积 w表示第i件物品的价值 int f[N][N]; // 所有状态 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; } - 优化方法---优化成一维数组来表述集合
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; const int N = 1010; int n, m; // n表示所有物品的个数 m表示背包的容量 int v[N], w[N]; // v表示第i件物品的体积 w表示第i件物品的价值 int f[N]; // 所有状态 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表示所有物品的个数 m表示背包的容量 int v[N], w[N]; // v表示第i件物品的体积 w表示第i件物品的价值 int f[N][N]; // 所有状态 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; } - 优化方法
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; const int N = 1010; int n, m; // n表示所有物品的个数 m表示背包的容量 int v[N], w[N]; // v表示第i件物品的体积 w表示第i件物品的价值 int f[N][N]; // 所有状态 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表示所有物品的个数 m表示背包的容量 int v[N], w[N], s[N]; // v表示第i件物品的体积 w表示第i件物品的价值,s[i]表示每件物品最多有s[i]个 int f[N][N]; // 所有状态 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：表示每件物品的个数最多有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; } - 优化方法--二进制优化方法
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; const int N = 25000, M = 2010; int n, m; // n表示所有物品的个数 m表示背包的容量 int v[N], w[N], s[N]; // v表示第i件物品的体积 w表示第i件物品的价值,s[i]表示每件物品最多有s[i]个 int f[N]; // 所有状态 int main(){ cin >> n >> m; int cnt = 0; for(int i = 1; i <= n; i++) { int a, b, s; // 体积 价值 个数 cin >> a >> b >> s; int k = 1; // 多重背包的二进制优化方法 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; } } // 优化版本的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 - 分组背包的算法框架---优化方法
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; const int N = 110; int n, m; // n表示所有物品的个数 m表示背包的容量 int v[N][N], w[N][N], s[N]; // v表示第i件物品的体积 w表示第i件物品的价值, S[i]:每组中物品的个数 int f[N]; // 从两维优化成一维 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--) // 改成一维表示状态时，从大到小来枚举所有体积！ 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; }
