1100: 解决采药

解题思路:

本题属于0/1背包问题，具体思路说不上，只需要记住两个公式即可

背包问题只考虑两种情况：采药/不采

dp[i][j]，其中i代表第i个物品，j代表剩余时间;(用于统计最后的数据)

cost[],采所花费的时间

value[],采所得到的价值

若采：dp[i][j]=dp[i-1][j-cost[i]]+value[i]   需要剩余时间>=所花费的时间

不采：dp[i][j]=dp[i-1][j]

最后通过公式代入for循环即可

注意事项:

参考代码:

#include<iostream>

using namespace std;

#include<cstring>//数组归零头文件

//#include<algorithm>//排序头文件

int main()

{

int T, M;//总时间/山洞草药数木

cin >> T >> M;

int cost[110] = {0};//采药花费的时间

int value[110] = {0};//所采药材的价值

int dp[110][1010];//统计结果(药材总数目，药材总时间)

memset(dp, 0, sizeof(dp));//数组归零

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

cin >> cost[i] >> value[i];

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

for (int j = 1; j < T + 1; j++)

{

if (j >= cost[i])//剩余时间>所需时间

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + value[i]);//比较采/不采

else//剩余时间不够

dp[i][j] = dp[i - 1][j];//不采

}

cout << dp[M][T];//输出

return 0;

}