AcWing 2. 01背包问题
原题链接
简单
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N], w[N];
int cap, n;
int main(){
cin >> n >> cap;
for (int i = 1; i <= n; i ++)
cin >> v[i] >> w[i];
int f[n + 1][cap + 1];
// 包含前0个物品显然f[0][*] = 0
for (int i = 0; i <= cap; i ++)
f[0][i] = 0;
// 状态计算: f[i][j] = max(f[i -1][j - v[i]] + w[i], f[i - 1][j])
for (int i = 1; i <= n; i ++)
{
for (int j = 0; j <= cap; j ++)
{
if (j - v[i] < 0)
f[i][j] = f[i - 1][j];
else
f[i][j] = max(f[i -1][j - v[i]] + w[i], f[i - 1][j]);
}
}
cout << f[n][cap] << endl;
return 0;
}