動态規劃之最大草藥價值

Description

小K是個苦命的孩子，他的師傅為了多賺錢，以減肥為理由，讓他去采藥，并說不完成不能吃飯。野地裡有許多不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。要求在規定的時間t裡，采到的草藥的總價值最大。

Input

第一行有2個整數T(1≤T≤1000)和M(1≤M≤100)，一個空格隔開，T代表總共能夠用來采藥的時間，M代表山洞裡的草藥的數目

接下來的M行每行包括兩個在1到100之間包括1和100）的整數，分别表示采摘某株草藥的時間和這株草藥的價值。

第二行共有n個整數。

Output

1個整數，表示在規定的時間内可以采到的草藥的最大總價值。

Sample Input

70 3

71 100

69 1

1 2

Sample Output

3

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1000 + 10;

int dp[maxn][maxn];  // dp[i][j]表示剩下時間為j第i個物品的最大價值
int time[maxn], value[maxn]; 
int t, m;


int main()
{
	cin >> t >> m;
	memset(time, 0, maxn);
	memset(value, 0, maxn);
	for(int i=1; i<=m; i++){
		cin >> time[i] >> value[i];
	}
	
	for(int i=1; i<=m; i++){
		for(int j=1; j<=t; j++){
			if(j<time[i])  // 所剩下的時間不足以采摘這個草藥 
				dp[i][j] = dp[i-1][j];
			else
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-time[i]]+value[i]); 
		}
	}
	
	cout << dp[m][t] << endl;

	return 0;
}