2.采药-01背包
[NOIP2005 普及组] 采药 - 洛谷
解题思路：
1.看到此题，很容易想到贪心算法的最优装载问题，那什么时候用贪心，什么时候用DP呢？贪心是比较“目光短浅”的，只考虑当前情况下应该放哪一株草药，那么在排序过程中，肯定是优先选择单位时间内价值更大的草药，当以这种策略选择的时候，每次的选择都是不可逆的，即当把价值比最高的放入背包后，不会再拿出来，而DP是根据背包的容量和价值随时在调整
2.举个例子：当背包容量为100的时候，有两株草药，时间和价值分别是20 90与100 100，很明显前者的价值比更高，但是一旦放入第一株草药后，第二株放不下了，可是放第二株才是正解，价值更高，通常遇到这种题目要去构造一组数据，利用反证等方法推翻一种策略
3.如果是DP问题，可以明显看出是01背包问题，每个物品只有一种，并且有两种选择，放或不放
4.设置状态：dp【i】【j】表示前i种物品在j时刻时的最大价值
5.状态转移：如果第i种物品不放的话，那么j时刻的价值也就是前i-1种物品的价值，即dp[i][j]=dp[i-1][j]，如果第i种物品放入的话，那么背包意味着牺牲容量，前i-1中的容量就缩小为j-tt[i]，然后再加上第i种物品的价值，放与不放取较大值，dp[i][j]=max(dp[i-1][j-tt[i]]+v[i]，dp[i-1][j])
6.初始状态：当时刻j为0的时候，那么价值为0，即dp[i][0]=0,当物品为0的时候，价值也为0 ，即dp[0][j]=0
7.求解目标值dp[m][T]
#include<bits/stdc++.h>
using namespace std;
int tt[110],value[110],dp[110][1005];
int main()
{
int t,m;
cin>>t>>m;
for(int i=1;i<=m;i++)//将每株草药的时间和价值存入数组
{
cin>>tt[i]>>value[i];
}
for(int i=1;i<=m;i++)//枚举每株草药
{
for(int j=1;j<=t;j++)//枚举每个时刻
{
if(j>=tt[i])//如果该时刻可以采摘这株草药
{
dp[i][j]=max(dp[i-1][j-tt[i]]+value[i],dp[i-1][j]);//选择较大价值
}
else
dp[i][j]=dp[i-1][j];//否则的话继承前i-1种草药的价值
}
}
cout<<dp[m][t];//输出目标值
return 0;
}