有 N 种物品和一个容量是 V的背包,每种物品都有无限件可用。
第 i 种物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,N,V用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行两个整数 vi,wi用空格隔开,分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围:
0<N,V≤10000
0<vi,wi≤10000
输入样例:
4 5
1 2
2 4
3 4
4 5
输出样例:
10
f[i][j]表示从前i个物品中选,选出的物品体积之和 <= j的最优解(价值最大)
所有物品的状态都只有 不选 ,选一个,选两个,选k个.......知道背包装不下为之:
所以从:
MAX : f[i -1][j] <不选第i个>、f[i -1][j - v[i]] + w[i]、f[i -1][j - 2 * v[i]] + 2 * w[i]、f[i -1][j - k * v[i]] + k * w[i -1] ...
但是这一个max函数中太多元素了,我们可以发现:
f[i][j - v[i]] <把j 看成j - v[i]> : 把v[i]看成本层的v,w[i]看成本层的w
对比f[i][j]=max: f[i - 1][j] , f[i - 1][j - v] + w , f[i - 1][j - 2v] + 2w , f[i -1][j - 3v] + 3w...
f[i][j - v]= max: f[i - 1][j - v] , f[i - 1][j - 2v] + w, f[i - 1][j - 3v] + 2w...
对比发现:f[i][j - v[i]]只是比f[i -1][j - v[i]] + w[i]、f[i -1][j - 2 * v[i]] + 2 * w[i]、f[i -1][j - k * v[i]] + k * w[i -1] ...
这一堆选1 2 3 4 k...到选不了为之的每一项少一个w[i],在max函数计算后最终结果少个w[i]
所以f[i -1][j - v[i]] + w[i]、f[i -1][j - 2 * v[i]] + 2 * w[i]、f[i -1][j - k * v[i]] + k * w[i -1] ... 这一坨可以等价替换成 f[i][j - v[i]] + w[i] 《注意这里第一维从上一次的 i - 1 换成本层的i了,所以优化成一维后要从小到大遍历,在遍历到 j 之前要先遍历到本层的 j - v[i],更新结果》
所以最终结果的不选:f[i - 1][j] 和 其他选1 ~ 选不了的个数 :f[i][j - v[i]] + w[i] 了;
其他细节与 01背包问题同理, j 从 0 ~ v[i] - 1可以省去遍历,只能选0个第i层物品,所以结果还等与上一层的f[j],结果不变不用再遍历一遍更新了,与 01背包主要区别就是要正着遍历,因为完全背包计算过程,推导结果 f[i][j] = max(f[i - 1][j],f[i][j - v[i]] + w[i]); 中 ,f[i] 为本层遍历结果
具体代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
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 = 0;j <= m;j ++ )
{
if(j >= v[i])
f[i][j] = max(f[i - 1][j],f[i][j - v[i]] + w[i]);
else
f[i][j] = f[i - 1][j];
}
cout << f[n][m] << endl;
return 0;
}
*/
// 优化写法
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 = v[i];j <= m;j ++ )
f[j] = max(f[j],f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}