赞
踩
有n种物品和一个容量是m的背包,每种物品都有无限件可用。第 i 种物品的体积是 vi,价值是 wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大,输出最大价值。
第i个物品可以选0~k个,其中k * v[i] ≤ j,(k + 1) * v[i] > j。
具体细节详看代码,如果有疑点可以回顾我之前写的0-1背包问题。
#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int w[N], v[N], f[N][N]; int n, m; 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 = 1; j <= m; j++){ for(int k = 0; k * v[i] <= j; k++){ // 当k == 0时,f[i - 1][j - k * v[i]] == f[i - 1][j],已经包含不选的情况了。 f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); } } } cout << f[n][m]; }
提示:最好不要直接从f[i, j] = Max(f[i - 1, j], f[i, j - v[i]] + w)这个经过“浓缩”的公式理解,这样反而会陷入困惑。
代码如下:
#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int w[N], v[N], f[N][N]; int n, m; 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 = 1; j <= m; j++){ f[i][j] = f[i - 1][j]; // f[i, j] = max(f[i - 1, j], f[i -1, j - v[i]] + w[i], f[i - 1, j - 2 * v[i]] + 2 * w[i], ...) // f[i, j - v[i]] = max( f[i - 1, j - v[i]], f[i - 1, j - 2 * v[i]] + w[i], ...) // 两者只差了一个w[i]。 if(v[i] <= j) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]); } } cout << f[n][m]; }
1、可见第i层仅仅使用到第i层的数据,所以可降至一维。
2、j - v[i] 和 j 都是小于等于j,所以从前到后遍历,即先把前面的数据更新为第i层数据,方才能调用第i层前面的数据。(区别0-1背包中从后到前,这里可以参考我之前写的0-1背包)
#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int w[N], v[N], f[N]; int n, m; 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 = v[i]; j <= m; j++){ // 1、可见第i层仅仅使用到第i层的数据,所以可降至一维。 // 2、j - v[i] 和 j 都是小于等于j,所以从前到后遍历,即先把前面的数据更新为第i层数据, // 方才能调用第i层前面的数据。(区别0-1背包中从后到前) f[j] = max(f[j], f[j - v[i]] + w[i]); } } cout << f[m]; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。