桐桑入梦


私信TA

用户名:wanggongsheng

访问量:91106

签 名:

2547668411@qq.com是我的邮箱,有问题可以用邮箱联系

等  级
排  名 7
经  验 16171
参赛次数 3
文章发表 163
年  龄 20
在职情况 学生
学  校
专  业

  自我简介:

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

方法一:
#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;
}






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





参考代码:

 

0.0分

2 人评分

  评论区