物品选取（pack）hgoi0527

2019-04-14 08:32发布

站内文章 / 模拟电子
17444 0 1246

物品选取（pack）hgoi0527 题解

题目描述

  • 小 X 确信所有问题都有个多项式时间算法，为了证明，他决定自己去当一次旅行商，在上路之前，
    小 X 需要挑选一些在路上使用的物品，但他只有一个能装体积为 m 的背包。显然，背包问题对小 X 来
    说过于简单了，所以他希望你来帮他解决这个问题。
    小 X 可以选择的物品有 n 样，一共分为甲乙丙三类：
    1．甲类物品的价值随着你分配给他的背包体积变化，它的价值与分配给它的体积满足函数关系式，
    v(x) = A*x^2-Bx，A，B 是每个甲类物品的两个参数。注意每个体积的甲类物品只有一个。
    2．乙类物品的价值 A 和体积 B 都是固定的，但是每个乙类物品都有个参数 C，表示这个物品可供
    选择的个数。
    3．丙类物品的价值 A 和体积 B 也是固定的，但是每个丙类物品可供选择的个数都是无限多个。
    你最终的任务是确定小 X 的背包最多能装有多大的价值上路。

输入

  • 第一行两个整数 n，m，表示背包物品的个数和背包的体积；
    接下来 n 行，每行描述一个物品的信息。第一个整数 x，表示物品的种类：
    若 x 为 1 表示甲类物品，接下来两个整数 A, B，为 A 类物品的两个参数；
    若 x 为 2 表示乙类物品，接下来三个整数 A，B，C。A 表示物品的价值，B 表示它的体积，C 表
    示它的个数；
    若 x 为 3 表示丙类物品，接下来两个整数 A，B。A 表示它的价值，B 表示它的体积。

输出

  • 输出一行，为一个整数，表示小 X 的背包能装的最大价值。

样例

  • 输入样例1
  • 4 10
    2 1 2 1
    1 1 2
    3 5 2
    2 200 2 3
  • 输出样例1
  • 610
  • 数据规模
  • 对于 50%的数据，只有乙和丙两类物品；
    对于 70%的数据，1<=n<=100, 1<=m<=500，0<=A,B,C<=200；
    对于 100%的数据，1<=n<=100, 1<=m<=2000，0<=A,B,C<=200。

题目解析

  • 第一眼看到题是懵逼的。
  • 这个甲类物品的设计有点颠覆我对背包问题的认知。
  • 用了各种数学方法也没有求出甲的最值……
  • 所以第一次打只拿了乙丙的60分。

然而

然而

然而！！！！！

甲类物品居然可以用枚举来得出答案？？？？？

又一次颠覆了我对背包问题的认知orz

为水数据烧香

  • 所以这只是正bian常tai的背包题而已
  • 简言之，就是根据物品的种类来分，使用完全，多重背包的方法就可以求出极值。
附上AC程序
给你们一个玄妙的程序你们自己体会。 #include #include #include #include using namespace std; const int LIMIT=110; int f[2000000]; int val[LIMIT],vlm[LIMIT],cnt[LIMIT]; int m,n; void finit(){ freopen("pack.in","r",stdin); freopen("pack.out","w",stdout); } int main(){ #ifndef LOCAL finit(); #endif scanf("%d%d",&n,&m); int t1; int kn=n; for (int i=1;i<=n;i++){ scanf("%d",&t1); if (t1==2){ scanf("%d%d%d",&val[i],&vlm[i],&cnt[i]); if (cnt[i]*vlm[i]>=m){ for (int j=vlm[i];j<=m;j++) f[j]=max(f[j],f[j-vlm[i]]+val[i]); }else{ int k=1; while (kfor (int j=m;j>=k*vlm[i];j--) f[j]=max(f[j],f[j-k*vlm[i]]+k*val[i]); cnt[i]-=k; k<<=1; } if (cnt[i]>0) for (int j=m;j>=cnt[i]*vlm[i];j--) f[j]=max(f[j],f[j-cnt[i]*vlm[i]]+cnt[i]*val[i]); } } else if (t1==3){ scanf("%d%d",&val[i],&vlm[i]); for (int j=vlm[i];j<=m;j++) f[j]=max(f[j],f[j-vlm[i]]+val[i]); }else if (t1==1){ int aa,bb; scanf("%d%d",&aa,&bb); for(int j=m;j>0;j--){ for(int k=j;k>=0;k--){ f[j]=max(f[j],f[j-k]+aa*k*k-bb*k); } } } } printf("%d",f[m]); return 0; }

热门文章