AcWing 2. 01背包问题
原题链接
简单
作者:
Auto
,
2021-01-27 23:28:28
,
所有人可见
,
阅读 278
空间优化版 + 解释为什么这样优化
#include <iostream>
using namespace std;
int n,m,v,w;
const int N = 1010;
int f[N]; // 前n个物品,体积不超过m时,能够带来的最大价值
int main()
{
cin >> n >> m;
f[0] = 0;
for(int i = 1;i <= n;i ++)
{
cin >> v >> w;
for(int j = m;j >= v;j --)
{
//1 2 3
f[j] = max(f[j - v] + w,f[j]);
/*
1 此时的f[j] 正在被计算,所以此时的f[j]是第i层的
2 此时的f[j - v]已经被计算过了,因为我们是从小到大算的
3 此时的f[j]已经被计算过,所以此时就是第i层的f[j]
综上,我们需要用到第i - 1层的f[j - v],所以我们要保证f[j - v]没有被计算过,所以
我们从大到计算就保证了再计算f[j]的时候,f[j - v]是肯定没被计算过的
*/
}
}
cout << f[m] << endl;
return 0;
}