时间限制: 1 s

空间限制: 32000 KB

题目等级 : 黄金 Gold

 

 

 

题目描述 

Description

  话说上回他给女孩送了n件礼物，由于是廉价的所以全部都坏掉了，女孩很在意这些礼物，所以决定自己缝补，但是人生苦短啊，女孩时间有限，她总共有m分钟能去缝补礼物。由于损坏程度不一样所以缝补的时间p也是不一样的，每件礼物呢，都有一个女孩的喜爱程度为w，后面还有一个数字h为这种礼物的件数。女孩想让自己的喜爱程度的和最大，那么请聪明的你帮她算一算！（注意：礼物非常多，不一定都能缝补完，女孩也不用把所有时间都花费）

输入描述 

Input Description

第1行2个整数 m,n

第2行到第n+1行 每行三个整数 p，w，h

输出描述 

Output Description

一个整数s表示最大的喜爱程度

样例输入 

Sample Input

8 2

2 100 4

4 100 2

样例输出 

Sample Output

400

 

数据范围及提示 

Data Size & Hint

m<=10000

n<=100

p,h,w<=6000

分类标签 Tags 

 

 

 

 

代码

#include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;int n,m,f[10001],t[101],like[101],sum[101];int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++)     scanf("%d%d%d",&t[i],&like[i],&sum[i]);    for(int i=1;i<=m;i++)     for(int j=n;j>=0;j--)       for(int k=0;k<=sum[i];k++)        {            if(j-k*t[i]<0) break;//要缝补这些礼物的前提是剩下的时间够缝补k个礼物的             f[j]=max(f[j],f[j-k*t[i]]+k*like[i]);//多重背包          }     printf("%d",f[n]);    return 0; }
              
             
            
           
          

思路：

  这个题是一个典型的多重背包的问题。

  缝补那个，缝补几个。。。

  所以我们要先判断时间够不够用，再从0到有的个数 开始找，找在时间允许的范围内的最大值

  注意：看清n,m分别代表的什么！！！！