动态规划—01背包

解题思路:

注意事项:

参考代码:

#include <stdio.h>

#define max(x,y) x>y?x:y//取最大值
int time[101] = { 0 };//采药时间
int value[101] = { 0 };//药材价值
int dp[101][1001] = { 0 };//动态规划—dp[i][j]==>>在j时间下，1-i药草中，采的药草的最大价值
//当i=0或j=0时，药材价值为0==>>dp[0][j]={0},dp[i][0]={0}

int main()
{
	int T = 0, M = 0;
	scanf("%d%d", &T, &M);
	for (int i = 1; i <=M; i++)
	{
		scanf("%d%d", &time[i], &value[i]);
	}
	for (int i = 1; i <= M; i++)
	{
		for (int j = 1; j <= T; j++)
		{
			//当拥有时间比要采的药材所用时间短时
			//则1--i药材在j时间内采得的最大价值等于1--i-1药材在j时间内采得的最大价值
			if (j < time[i])
			{
				dp[i][j] = dp[i - 1][j];
			}
			//当拥有时间足够采i药材时，则有两种选择采i或不采i
			//1、采i：则1--i药材在j时间内采得的最大价值等于1--i-1药材在（j-采i所用的时间）的时间内采得的最大价值+i的价值
			//2、不采i：则1--i药材在j时间内采得的最大价值等于1--i-1药材在j时间内采得的最大价值
			//3、取两种情况的较大值
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - time[i]] + value[i]);
			}
		}
	}
	printf("%d", dp[M][T]);//打印1--M株草药在T时间内采的最大价值

	return 0;
}