AcWing 2. 01背包问题
原题链接
简单
作者:
chenjiaqiy
,
2023-11-18 21:35:35
,
所有人可见
,
阅读 41
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m; //个数和背包容量
int v[N],w[N]; //每个物品的体积和价值
int f[N]; //表示状态
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; //读入所有的物品
// f[0][0 ~ m] = 0; //0个没有意义,且全局变量已经初始化
//f[i][j] 表示从1~i的数,总价值不超过j的集合
for (int i = 1; i <= n; i ++ ) //枚举个数
for (int j = m; j >= v[i]; j -- ) //枚举体积
{
//f[j] = f[j],去掉了f[i]那一层
//要使得j >=v[i]才有结果,所以可以让循环从j = v[i]开始
//但由于j - v[i] < v[i],所以在这第i层循环中已经被遍历过了
//等价于 f[i][j] = max(f[i - 1][j],f[i][j - v[i]] + w[i]),但正确的是f[i - 1];
//所以将其反过来遍历一次,此时 j -v[i] > v[i],没有在之前被遍历过
//if(j >= v[i]) f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]);
f[j] = max(f[j],f[j - v[i]] + w[i]);
}
cout << f[m] << endl;
return 0;
}