物品选取(pack)hgoi0527

物品选取(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 <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
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 (k<cnt[i]){
                    for (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;
}


发表评论

电子邮件地址不会被公开。 必填项已用*标注