采药-题解(C++代码)

典型背包问题

1.当药草可以随便取的时候（题目中不是）

不需要考虑药草个数问题
dp[i]:代表i内时间取得的药草之和最大值；
h[j].t:代表第j颗药草所花时间 v代表对应价值
i从小到大逐渐循环求出题目中所要求的时间t内的最大价值
j无所谓
则建立方程
dp[i]=max(dp[i],dp[i-h[j].t]+h[j].v);
eg:题目中70时间内价值和=1时间内价值和+1 或 69时间内价值和+2取其中最大值

2.当指定药草数量的时候（题目）

需要2维数组额外记录取到的第几个草药 药草标识i在最外层循环
dp[i][j]:考虑前i颗草药在所有时间段内的最大价值 一直迭代到考虑所有药草
则在时间j内，第i颗草药可以取可以不去取，取两种情况下的最大值
时间j仍是从小到大 药草标识i在最外层
dp[i][j] = max(dp[i-1][j],dp[i-1][j-h[i].t]+h[i].v);
滚动数组；
取第一个草药所有符合的时间加入第一个价值，
第i颗草药符合的时间加入价值且剩余时间能取得最大值也可以加入 计算最大值
dp[j]=max(dp[j],dp[j-h[i].t]+h[i].v);

#include<iostream>
#include<string.h>
using namespace std;
/*     背包问题 
dp[i][j] = max(dp[i-1][j],dp[i-1][j-h.t]+h.v);
或滚动数组；
取第一个草药所有符合的时间加入第一个价值，
第i颗草药符合的时间加入价值且剩余时间能取得最大值也可以加入 计算最大值 
dp[j]=max(dp[j],dp[j-h[i].t]+h[i].v);
*/
struct herb{
    int t;
    int v;
};
int dp[1001];
int main(){
    int T,M;
    struct herb h[101];  
    cin>>T>>M;
    for(int i=1;i<=M;i++){
        cin>>h[i].t>>h[i].v;
    }
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=M;i++){
        for(int j=T;j>=0;j--){
            if(j>=h[i].t){
                dp[j]=max(dp[j],dp[j-h[i].t]+h[i].v);
            }
        }
    }
    cout<<dp[T]<<endl;
}