【codevs】3269 混合背包

小鱼儿 2022-06-18 07:50 150阅读 0赞

> 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

> 多重背包，考虑：如果mi\*vi >= V 那么按照完全背包来做；否则，二进制拆分，再按照01背包来做。

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn =  200005;
    struct node
    {
        int vi;
        int wi;
        int mi;
    }vis[205];
    int n,v;
    int dp[maxn];
    void zero_one_package(int ww,int vv)
    {
            for(int j=v;j>=vv;j--)
        {
            dp[j]=max(dp[j],dp[j-vv]+ww);
        }
    }
    
    void complete_package(int ww,int vv)
    {
        for(int j=vv;j<=v;j++)
            dp[j]=max(dp[j],dp[j-vv]+ww);
    }
    void multi_package(int ww,int vv,int mm)
    {
        if(mm*vv >= v)
            complete_package(ww,vv);
        else
        {
            int k=1;
            while(k <= mm)
            {
                zero_one_package(k*ww,k*vv);
                mm -=k;
                k = 2*k;
              // k <<= 1;
            }
            zero_one_package(mm*ww,mm*vv);
        }
    }
    int main()
    {
        cin>>n>>v;
        for(int i=1;i<=n;i++)
        {
            cin>>vis[i].vi>>vis[i].wi>>vis[i].mi;
        }
        for(int i=1;i<=n;i++)
        {
            if(vis[i].mi == 1)
                zero_one_package(vis[i].wi,vis[i].vi);
            else if(vis[i].mi ==-1)
                complete_package(vis[i].wi,vis[i].vi);
            else multi_package(vis[i].wi,vis[i].vi,vis[i].mi);
        }
        cout<<dp[v]<<endl;
        return 0;
    }