#C++1100——采药（01背包问题）

参考代码:

#include <iostream>
#include <cstring>
#include <algorithm>
typedef int ii; //给数据类型起别名 
using namespace std;//01背包问题(动态规划) 
int main()
{
	int totaltime,totalnum;
	ii value[105],time[105];
	cin>>totaltime>>totalnum;
	int dp[totaltime+1][totalnum+1];//从0开始保存，从1开始计算，故至少加一保证数组够大 
	for(int i=0;i<totalnum;i++)
	{
		cin>>time[i]>>value[i];
	}
	memset(dp,0,sizeof(dp));//初始化dp（状态）数组 
	for(int i=1;i<=totaltime;i++)
	{
		for(int j=1;j<=totalnum;j++)//dp[i][j]表示[i]时间内采[j]种草药的价值 
		{
			dp[i][j]=dp[i][j-1];//新状态继承上一状态 
			if(i>=time[j-1])//如果可以采 
			{
				dp[i][j]=max(dp[i-time[j-1]][j-1]+value[j-1],dp[i][j-1]);//要采时间减少，价值增加，不采则还是上一状态 
			}
		}
	}
	cout<<dp[totaltime][totalnum]; 
}