AcWing 426. 开心的金明 | 0-1背包问题
原题链接
简单
作者:
我要出去乱说
,
2021-01-31 22:10:42
,
所有人可见
,
阅读 357
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30010;
int n, m;
int f[N];
int main()
{
scanf("%d%d", &n, &m); //n代表总预算金额,m代表物品总数,每件物品只需要买一次
while (m -- )
{
int v, w; //v为物品价值,w为权重,即物品重要度
scanf("%d%d", &v, &w);
w *= v; //v下面还会用到,故用w来存价值与重要度的乘积,省得再开一个变量来存
for (int j = n; j >= v; j -- ) //当前状态与上一状态有关,所以从后往前遍历
f[j] = max(f[j], f[j - v] + w); //买当前物品和不买当前物品两种情况中取最大值
}
printf("%d\n", f[n]);
return 0;
}