题解 | 【模板】01背包（动态规划）

#牛客春招刷题训练营# + 链接

动态规划经典问题

第0阶段只有0体积设置为0，其他都设置为负无穷即可。

#include <bits/stdc++.h>
using namespace std;

const int INF=1e9;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> dp(m + 1, -INF);
    vector<int> v(n), w(n);
    for (int i = 0; i < n; i++)
        cin >> v[i] >> w[i];
    dp[0] = 0;
    for (int i = 0; i < n ; i++) {
        for (int j = m; j >= v[i]; j--) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
    cout << max(0, dp[m]) << endl;
    return 0;
}