背包(pack)hgoi0501

背包(pack)hgoi0501 题解


题目描述

  • 你有一个容量为 M 的背包,和 N 种物品。
    每种物品都有三个属性,Vi Wi Ci,分别表示这种物品的体积、价值和件数。
    你的任务是,从这些所给物品中,选出若干件,其体积之和不能超过背包容量,并且使
    所选物品的权值的和最大。。

输入

  • 输入数据的第一行是两个整数 M; N,表示物品的种类数和背包的容量。
    接下来的 M 行,每行描述了一种物品的价值 Wi、体积 Vi 和件数 Ci。
    ##输出
  • 输出一个整数,表示最大权值总和,保证该值不超过 32 位带符号整数。

样例

  • 输入样例1
  • 2 30
    50 20 2
    51 10 4
  • 输出样例1
  • 153

题目解析

  • 多重背包模板题
  • 参考Tianyi Cui的背包问题九讲,程序采用了二进制的优化,将多重背包化为完全背包和01背包做。
  • 将一个重量为w有c个的物体,可以将它分成2的幂次数与一个常数相加的结果,于是这些物品可以组合出1到c所有可能的数字。所以这些物品的质量就是w*k,k为分离出的每一个数。
  • 如13分解成1 2 4 6
  • 而如果w*c已经大于了最大容量,那个数不再是主要的限制量,主要限制量变为最大容量,即可当完全背包做。
  • 同样也采用了滚动数组来节省空间。

附上AC程序
可以忽略最开始的优化
该程序依然存在被卡二分常数的可能导致超时。
对此可以采用单调队列优化来解决
程序暂未给出
时间复杂度O(mn log(c))

#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define ENS //__attribute__((optimize("-O2")))
#define NES //__attribute__((optimize("-O2"))) __inline__ __attribute__((always_inline))
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
NES void finit(){
    freopen("pack.in","r",stdin);
    freopen("pack.out","w",stdout);
}
long n,m,a[0x2711],c[0x2711],w[0x2711];
long f[0x7fffff];
ENS int main(){
    finit();
    scanf("%ld%ld",&n,&m);
    for (int i=1;i<=n;++i)
        scanf("%ld%ld%ld",w+i,a+i,c+i);
    memset(f,0,sizeof(f));
    for (int i=1;i<=n;++i){
        if (a[i]*c[i]>=m)
            for (int j=a[i];j<=m;++j)
                f[j]=max(f[j],f[j-a[i]]+w[i]);
        else{
            int k=1;
            while (k<c[i]){
                for (int j=m;j>=a[i]*k;--j)
                    f[j]=max(f[j],f[j-a[i]*k]+w[i]*k);
                c[i]-=k;
                k<<=1;
            }
            for (int j=m;j>=c[i]*a[i];--j)
                f[j]=max(f[j],f[j-a[i]*c[i]]+w[i]*c[i]);
        }
    }
    cout<<f[m];
    return 0;
}

—–****


发表评论

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