题解 | 采药

//普通的01背包问题  
//注意状态转移方程的写法   
//时间够：  装与不装    dp[i][j]=max(dp[i-1][j],dp[i-1][j-times[i]]+weight[i])
//时间不够：   当前状态由 没有遍历到该物品时的最大价值相同
#include<iostream>
#include<math.h>
using namespace std;
int dp[101][1001];//dp[i][j] 表示在j时间内有i件草药的前提下能采摘的最大价值。
int times[1001];
int weight[101];
int main(){
    int T,M;
    cin>>T>>M;
    for(int i=1;i<=M;i++){
        cin>>times[i]>>weight[i];
    }
    for(int i=1;i<=M;i++){  //第i件草药
        for(int j=1;j<=T;j++){  //j时间内
            if(j>=times[i]){
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-times[i]]+weight[i]);
            }else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    cout<<dp[M][T];
    return 0;
}