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;
}