采药

思路

这个和 点菜问题 一样，也是 0-1 背包问题，这里就不进行赘述了，用 dp[i][j] 表示限时 j 采前 i 种药的最大总价值，那最后求出来 dp[M][T] 就好了

• 不采第 i 种药：
• 采第 i 种药：

因为前面已经说过如果进行空间复杂度的优化，这里我就直接写出优化后的版本了。

#include<iostream>
#include<vector>

using namespace std;

int main(){
    int T, M;
    while(cin >> T >> M){
        vector<pair<int, int>> herbs;
        int time, value;
        for(int i = 0; i < M; i ++){
            cin >> time >> value;
            herbs.emplace_back(time, value);
        }
        vector<int> dp(T + 1, 0);
        for(int i = 0; i < M; i ++){
            for(int j = T; j >= herbs[i].first; j --)
                dp[j] = max(dp[j], dp[j - herbs[i].first] + herbs[i].second);
        }
        cout << dp[T] << endl;
    }
    return 0;
}