增肥计划

问题描述

某队长需要设计一个增肥计划，于是去考察 T 家养生店的增肥产品。不同的养生店都把自己的增肥药药效吹上了天，搞饥饿营销，漫天要价，但见多识广的队长分分钟看出实际药效，并拿了个小本子记了下来。他对店里还有的 N 种增肥药进行统计，把每种增肥药的实际药效抽象为一个正整数 w[i]，同时把剩余药品数量 u[i]、价格 p[i]抄了下来。由于去不同家养生店的路费浪费了大把经费，每家养生店能用的经费不同，记为 M。因为队长日理万 ‘鸡’，就把这件事交给你啦，请你对每家养生店分别计算在预算允许的情况下，购买的增肥产品实际药效最好是多少？计算完后队长要你提供预估花费，由于你相信队长的眼光并为队长的身体着想，你打算用 8 进制保存结果，这样计划药效会显得比较大，也许他会坚持增肥？

输入格式

第一行一个数 T，代表 T 家养生店。接下来是 T 家养生店的具体描述，在每家养生店能用的活动经费 M，增肥药种类数 N。然后 N 行描述增肥药，数量 u,价格 p,药效 w。

输出格式

共 T 行，每行一个数，描述计划药效

样例输入

1 1

1 1 1

样例输出

题解

典型的多重背包。

但是看数据范围把多重背包拆成01背包来做会TLE的，所以加个二进制优化。

所谓二进制优化，就是每种药品有u[i]件，分成几份，使这几份可以凑成1~u[i]的任意一个数。例如，一种药品有7件，可以分成3份，每份分别有1,2,4件。把每份当成一件，再用01背包，效率会提高很多。

结果要用8进制表示，其实不用手动转， “%o”就可以直接把十进制转成八进制。

 1 #include <cstring>
 2 #include <string>
 3 #include <cstdio>
 4 int T,m,n,u[68005],w[68005],c[68005],f[5005],a[50];
 5 int max(int x,int y)
 6 {
 7     return x>y?x:y;
 8 }
 9 int main()
10 { 
11    
12     int i,j,k,x,y,z;
13     scanf("%d",&T);
14     while (T--)
15     {
16         memset(f,0,sizeof(f));
17         scanf("%d%d",&m,&n);
18         for (i=1,k=0;i<=n;i++)
19         {
20             scanf("%d%d%d",&x,&y,&z);
21             for (j=1;j<=x;j*=2)
22               w[++k]=y*j,c[k]=z*j,x-=j; 
23             if (x) w[++k]=y*x,c[k]=z*x;   //printf("k=%d
",k);
24         }
25         n=k;  
26         for (i=1;i<=n;i++)
27           for (j=m;j>=w[i];j--)
28           //  for (k=1;k<=u[i] && k*w[i]<=j;k++)
29               f[j]=max(f[j],f[j-w[i]]+c[i]);
30         printf("%o
",f[m]);         
31     }
32     return 0;
33 }