P2871 [USACO07DEC]Charm Bracelet S

Link

Solution

01背包

Code

#include <algorithm>
#include <iostream>
using namespace std;

int dp[13000], c[3500], w[3500];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> c[i] >> w[i];
    for (int i = 0; i <= m; i++) dp[i] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= c[i]; j--)
                dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
    cout << dp[m] << endl;
    return 0;
}