采药 （C++代码）

解题思路:贪心算法不适合这题，使用动态规划（递归的一种类似形式）

方法一：
#include<iostream>
# include<cstring>
# define max(a,b) ( a )>( b )?( a ): (b)
using namespace std;
int main()
{

    int dp[101][1001] , n , t ,  a [101],v[101] ,  i ,  j;   // dp[已经判断是否摘取的草药数量][剩余的时间]
    cin >> t >> n;
    for(i=1;i<=n;i++)
        cin  >> a[i]  >>  v[i] ;
    memset( dp , 0 , sizeof(dp)) ;
    for(i=1;i<=n;i++)
     for(j=0;j<=t;j++)  //这个的j 对应着剩余的时间
    {
        if( j >= a [i])   dp[i][j] = max (  dp[i-1][j]  , dp[i-1][j-a[i]] + v[i] ) ;//放还是不放的选择，如果时间允许采药
        else  dp[i][j] = dp[i-1][j] ;   //时间不允许采药
     }
     cout<<dp[n][t]<<endl;  
     return 0;
}
方法二：使用递归（递归算法容易超时，但时简单易懂）

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[1000 ]  , b[1000]  ; //a 记录 时间 ，b 记录 价值
int fac(int  n , int  t)
{
        int m = 0 ;
       if ( n == 0 || t == 0)      return 0;  // 边界
       if (a[n-1] >  t )               return fac(n-1 , t );    // 时间不可以允许摘这个草药
       if(a[n-1] <= t)               m =  max(fac(n-1 , t - a[n-1] ) + b[n-1] ,  fac( n - 1 , t) );
       return m;
}
int main(void)
{
    int t , n  , i , sum = 0 ;
    cin >>  t  >> n ;
    for(i=0;i<  n ;i++)  cin >>  a[i]  >> b[i] ;
    sum = fac ( n , t );
    cout << sum << endl;
    return 0;
}

注意事项:对于数据量大的，递归超时





参考代码: