1.链接地址：
http://bailian.openjudge.cn/practice/2773/
http://bailian.openjudge.cn/practice/2726/
http://bailian.openjudge.cn/practice/2727/
2.题目：
- 总Time Limit:
- 1000ms
- Memory Limit:
- 65536kB
- Description
- 辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出 了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给 你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
- Input
- 输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <=
100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采
摘某株草药的时间和这株草药的价值。- Output
- 输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
- Sample Input
71 100
69 1
1 2- Sample Output
- Source
- NOIP 2005
3.思路：
背包问题，dp模板题
由于规模小，直接使用未优化的背包问题解法即可
4.题目：
提供两个版本的答案
（1）未优化数组的，比较容易看懂
#include <iostream>
#include <cstdio> using namespace std; int main()
{
//freopen("C://input.txt","r",stdin); int i,j; int t,m;
cin >> t >> m; int *arr_time = new int[m];
int *arr_value = new int[m]; for(i = ;i < m; ++i) cin >> arr_time[i] >> arr_value[i]; int **dp = new int*[m];
for(i = ;i < m; ++i) dp[i] = new int[t + ]; for(i = ; i < arr_time[m - ] && i <= t; ++i) dp[m - ][i] = ;
for(i = arr_time[m - ]; i <= t; ++i) dp[m - ][i] = arr_value[m - ]; for(i = m - - ; i >= ; --i)
{
for(j = ; j < arr_time[i] && j <= t; ++j) dp[i][j] = dp[i + ][j];
for(j = arr_time[i]; j <= t; ++j) dp[i][j] = dp[i + ][j] > (dp[i + ][j - arr_time[i]] + arr_value[i]) ? dp[i + ][j] : (dp[i + ][j - arr_time[i]] + arr_value[i]);
} int max = ;
for(j = ; j <= t; ++j) if(max < dp[][j]) max = dp[][j]; cout << max << endl; for(i = ; i < m; ++i) delete [] dp[i];
delete [] dp; delete [] arr_time;
delete [] arr_value; return ;
}
（2）优化数组的
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std; int main()
{
//freopen("C://input.txt","r",stdin); int i,j; int t,m;
cin >> t >> m; int *arr_time = new int[m];
int *arr_value = new int[m]; for(i = ;i < m; ++i) cin >> arr_time[i] >> arr_value[i]; int *dp = new int[t + ];
memset(dp,,sizeof(int) * (t + )); for(i = m - ; i >= ; --i)
{
for(j = t; j >= arr_time[i]; --j) dp[j] = dp[j] > (dp[j - arr_time[i]] + arr_value[i]) ? dp[j] : (dp[j - arr_time[i]] + arr_value[i]);
} int max = ;
for(j = ; j <= t; ++j) if(max < dp[j]) max = dp[j]; cout << max << endl; delete [] dp; delete [] arr_time;
delete [] arr_value; return ;
}