AcWing 426. 开心的金明
原题链接
简单
作者:
我是java同学
,
2023-02-14 18:54:40
,
所有人可见
,
阅读 130
dp
- 集合:
f[i][j]
:从前i
件物品中选,且总价格不超过j
的乘积总和最大的方案
- 状态计算:
- 不选
i
:f[i - 1][j]
- 选
i
:f[i - 1][j - v[i]] + v[i] * w[i]
;
二维
#include <iostream>
using namespace std;
const int N = 30, M = 30010;
int n, m;
int f[N][M];
int main()
{
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i ++ )
{
int v, w;
cin >> v >> w;
for (int j = 0; j <= m; j ++ )
{
f[i][j] = max(f[i - 1][j], f[i][j]);
if (j >= v) f[i][j] = max(f[i][j], f[i - 1][j - v] + v * w);
}
}
printf("%d\n", f[n][m]);
return 0;
}
一维
#include <iostream>
using namespace std;
const int M = 30010;
int n, m;
int f[M];
int main()
{
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i ++ )
{
int v, w;
cin >> v >> w;
for (int j = m; j >= v; j -- )
f[j] = max(f[j], f[j - v] + v * w);
}
printf("%d\n", f[m]);
return 0;
}