AcWing 2. 01背包问题

一定要看的视频讲解：↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

【E08【模板】背包DP 01背包——信息学竞赛算法】

i表示放入i个物品，j表示第j个物品，用于访问体积v【j】

#include <iostream>
#include <algorithm>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];for (int i = 1; i <= n; i ++ )for (int j = m; j >= v[i]; j -- )f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[m] << endl;return 0;
}