题目描述 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

【思路】多重背包问题 直接上模板
f[m]为不超过m分钟喜爱程度的最大值
【代码】
#include<iostream>
#include<cstdio>
using namespace std;
int w[],t[],c[],f[];
int main()
{
int m,n;
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++)
scanf("%d%d%d",&t[i],&w[i],&c[i]);
for(int i=;i<=n;i++)
{
for(int j=m;j>=t[i];j--)
{
for(int k=;k<=c[i];k++)//看看同种缝几个最大 循环从0开始 因为也可以不缝这一种嘛
{
if(j-k*t[i]<)break;
f[j]=max(f[j],f[j-k*t[i]]+k*w[i]);
}
}
}
printf("%d",f[m]);
return ;
}
05-14 16:45