【C++】采药 动态规划思路

解题思路:其实最开始我（蒟蒻）看到这道题想用贪心来做，结果贪心是真的不适合寻找全体的最优解。深搜的话感觉还是有些复杂，要保留记忆，所以便使用动态规划来求，这样其实还挺简单的。代码不长也比较好理解。（baka琪露诺也能看懂的x

注意事项:其实本题非常像01背包那道题，但是难度要低好多。

参考代码:

#include <iostream>

#include<bits/stdc++.h>

using namespace std;

int T, M;

int Ti[105], V[105];

int dp[1005];//动态规划数组

int main()

{

cin >> T >> M;

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

{

cin >> Ti[i] >> V[i];

}

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

{

for (int j = T;j >= Ti[i];j--)

{

dp[j] = max(dp[j - Ti[i]] + V[i], dp[j]);//不超过时间就加上药的价值取最大

}

}

cout << dp[T];

}