2503 失恋28天-缝补礼物

 

题目描述 

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

多重背包裸题

/*转化成01背包*/#include
          
           #include
           
            using namespace std;#define maxm 10010#define maxn 110int n,m,w[maxn*20],v[maxn*20],cnt,dp[maxm];int main(){
             scanf("%d%d",&m,&n);    for(int i=1;i<=n;i++){        int s=1;int a,b,c;        scanf("%d%d%d",&a,&b,&c);        while(c-s>=0){            c-=s;            w[++cnt]=s*a;            v[cnt]=s*b;            s<<=1;        }        if(c)w[++cnt]=c*a,v[cnt]=c*b;    }    for(int i=1;i<=cnt;i++){        for(int j=m;j>=0;j--){            if(j-w[i]<0)break;            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);        }    }    printf("%d",dp[m]);    return 0;}
           
          

/*果的多重背包*/#include
          
           #include
           
            using namespace std;#define maxm 10010#define maxn 110int n,m,w[maxn],v[maxn],h[maxn],dp[maxm];int main(){    freopen("Cola.txt","r",stdin);    scanf("%d%d",&m,&n);    for(int i=1;i<=n;i++)scanf("%d%d%d",&w[i],&v[i],&h[i]);    for(int i=1;i<=n;i++){        for(int j=m;j>=0;j--){            for(int k=0;k<=h[i];k++){                if(j-k*w[i]<0)break;                dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);            }        }    }    printf("%d",dp[m]);    return 0;}