信息学奥赛一本通T1290-采药(01背包)

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

const int MAX = 1001;

int T, M;

int t[MAX], v[MAX];

int dp[MAX] = {0};

int solve(int T, int M)

{

    for (int i = 1; i <= M; i++) {

        for (int j = T; j > 0; j--) {

            if (j >= t[i]) {

                dp[j] = max(dp[j], dp[j - t[i]] + v[i]);

            }

        }

    }

    return dp[T];

}

int main()

{

    cin >> T >> M;

    for (int i = 1; i <= M; i++) {

        cin >> t[i] >> v[i];

    }

    memset(dp, 0, sizeof(dp));

    cout << solve(T, M) << endl;

    return 0;

}