1100采药(dp记忆化搜索）

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int MAXT = 1005;

const int MAXM = 105;

int T;

int M;

int arr[MAXM];//存每种药采摘的时间

int brr[MAXM];//存每种药的价值

int dp[MAXT];

//int dfs(int i, int t)

//{

// if (i > M)

// return 0;

// else

// {

// if (t < arr[i])

// return dfs(i + 1, t);

// else if (t >= arr[i])

// return max(dfs(i + 1, t), dfs(i + 1, t - arr[i]) + brr[i]);

// }

//}

int main()

{

cin >> T >> M;

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

{

cin >> arr[i] >> brr[i];

}

for (int i = 1; i <= M; i++)//第几种药

{

//剩余的采药时间

//判断条件是 剩余时间大于或等于采药时间

//这里采用的是记忆化搜素

//而我也为大家写了dfs的求法，不过会时间超时，大家看看就行

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

{

dp[j] = max(dp[j], dp[j - arr[i]] + brr[i]);

   }

}

cout << dp[T];

/*int res = dfs(1, T);

cout << res;*/

return  0;

}