多重背包问题 I
题目要求
题目描述：
输入格式：
输出格式：
输出一个整数，表示最大价值。
数据范围：
输入样例：
4 5 1 2 3 2 4 1 3 4 3 4 5 2
输出样例：
10
思路分析
数据范围很小，暴力枚举即可，不需要过多操作，f[i][j] 代表的是只从前 i 件物品中选，且总体积不超过 j的价值最大值。
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 110; int f[N][N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) { int v, w, s; cin >> v >> w >> s; for (int j = 0; j <= m; j ++ ) for (int k = 0; k <= s && k * v <= j; k ++ ) f[i][j] = max(f[i][j], f[i - 1][j - k * v] + k * w); } cout << f[n][m] << endl; return 0; }
代码优化
滚动数组
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 110; int f[2][N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) { int v, w, s; cin >> v >> w >> s; for (int j = 0; j <= m; j ++ ) for (int k = 0; k <= s && k * v <= j; k ++ ) f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - k * v] + k * w); } cout << f[n & 1][m] << endl; return 0; }
拷贝数组
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 110; int f[N], g[N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) { int v, w, s; cin >> v >> w >> s; memcpy(g, f, sizeof f); for (int j = 0; j <= m; j ++ ) for (int k = 0; k <= s && k * v <= j; k ++ ) f[j] = max(f[j], g[j - k * v] + k * w); } cout << f[m] << endl; return 0; }
逆循环优化
逆循环的优化方式和 01 背包的优化是相同的，原理也是一致的，对于体积逆序枚举即可实现，这样的优化方法可真正实现仅用一维数组表示二维变量：
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 110; int f[N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) { int v, w, s; cin >> v >> w >> s; for (int j = m; ~j; j -- ) for (int k = 0; k <= s && k * v <= j; k ++ ) f[j] = max(f[j], f[j - k * v] + k * w); } cout << f[m] << endl; return 0; }
