P1616 疯狂的采药

Link

Solution

完全背包

Code

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

int dp[1000010], c[10010], w[10010];

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