首页 > 代码库 > 模板——混合背包

模板——混合背包

2024-08-21 07:03:14   214人阅读

http://codevs.cn/problem/3269/

3269 混合背包

 

 时间限制: 1 s
 空间限制: 256000 KB
 题目等级 : 钻石 Diamond
 
【题目描述】Description

　　背包体积为V ,给出N个物品，每个物品占用体积为Vi,价值为Wi,每个物品要么至多取1件，要么至多取mi件（mi > 1） , 要么数量无限 ， 在所装物品总体积不超过V的前提下所装物品的价值的和的最大值是多少？

【输入描述】 Input Description

　　第一行两个数N,V,下面N行每行三个数Vi,Wi,Mi表示每个物品的体积，价值与数量，Mi=1表示至多取一件，Mi>1表示至多取Mi件，Mi=-1表示数量无限

【输出描述】 Output Description

　　1个数Ans表示所装物品价值的最大值

【样例输入】 Sample Input

　　2 10

　　3 7 2

　　2 4 -1

【样例输出】 Sample Output

　　22

【数据范围及提示】 Data Size & Hint

　　对于100%的数据,V <= 200000 , N <= 200

 

#include <cstdio>#include <cstring>#include <iostream>using namespace std;int V,n;int w[210],v[210],m[210];int f[200010];int main(){    scanf("%d%d",&n,&V);    for(int i=1;i<=n;i++)        scanf("%d%d%d",&w[i],&v[i],&m[i]);    for(int i=1;i<=n;i++)    {        if(m[i]==-1)//完全背包             for(int j=w[i];j<=V;j++)                f[j]=max(f[j],f[j-w[i]]+v[i]);        else//01与多重背包         {            int x=m[i];            for(int k=1;k<=x;k<<=1)            {                for(int j=V;j>=w[i]*k;j--)                    f[j]=max(f[j],f[j-w[i]*k]+v[i]*k);                x-=k;            }            if(x)                for(int j=V;j>=w[i]*x;j--)                    f[j]=max(f[j],f[j-w[i]*x]+v[i]*x);        }    }    cout<<f[V];    return 0;}

 

模板——混合背包


联系
我们