采药 （C++代码）

解题思路:  0/1背包问题

参考代码:

#include <iostream>
#include<cmath>
using namespace std;
int T,M,ValueSum;
int dp[1002][1002];
int value[102],tim[102];
int get_MaxValue(int m,int t);
int main()
{
    cin>>T>>M;
    for(int i=0;i<=M;++i)
    {
        for(int j=0;j<=T;++j)
        dp[i][j]=-1;
    }
    for(int i=1;i<=M;++i)
            cin>>tim[i]>>value[i];
    ValueSum=get_MaxValue(1,T);
    cout<<ValueSum<<endl;
    return 0;
}
int get_MaxValue(int m,int t)
{
    if(dp[m][t]>0) return dp[m][t];
    if(m==M) dp[m][t]=t>=tim[m]?value[m]:0;
    else{
        if(t>=tim[m]) dp[m][t]=max(get_MaxValue(m+1,t),get_MaxValue(m+1,t-tim[m])+value[m]);
        else dp[m][t]=get_MaxValue(m+1,t);
    }
    return dp[m][t];
}