采药 （C语言代码）

解题思路:01背包算法：最优解

注意事项:

参考代码:

#include<stdio.h>
int S[101][1001];
int Mvalue[101];
int Mtime[101];
int main()
{
	int T,M;
	scanf("%d%d",&T,&M);
	for(int i=1;i<=M;i++)
		scanf("%d%d",&Mtime[i],&Mvalue[i]);
	for(int i=1;i<=M;i++)
		for(int j=1;j<=T;j++){
			if(j-Mtime[i]<0)
				S[i][j]=S[i-1][j];
			else if((S[i-1][j-Mtime[i]]+Mvalue[i])>S[i-1][j])
				S[i][j]=S[i-1][j-Mtime[i]]+Mvalue[i];
			else
				S[i][j]=S[i-1][j];
		}
	printf("%d",S[M][T]);
	return 0;
}