题目描述

一个简简单单的混合背包问题。
（01背包，完全背包，多重背包问题的结合）

样例

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

8

算法1

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int N,V,cnt;
int f[1010];
int jz[10100],tj[10100];
int main()
{
    cin>>N>>V;
    for(int i=1;i<=N;i++)
    {
        int v1,v2,v3;
        cin>>v1>>v2>>v3;
        if(v3==0)
        {
            for(int j=v1;j<=V;j++)
            {
                f[j]=max(f[j],f[j-v1]+v2);//如果是完全背包，那么就直接完全背包问题解决
            }
        }
        else if(v3==-1)//加入是01背包
        {
           cnt++;
           jz[cnt]=v2;
           tj[cnt]=v1;
        }
        else
        {
            //二维优化
            int k=1;
            while(k<=v3)
            {
                cnt++;
                jz[cnt]=v2*k;
                tj[cnt]=v1*k;
                v3=v3-k;
                k=k*2;
            }
            if(v3>0)
            {
                cnt++;
                jz[cnt]=v2*v3;
                tj[cnt]=v1*v3;
            }
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=V;j>=tj[i];j--)
        {
            f[j]=max(f[j],f[j-tj[i]]+jz[i]);//最后再做一遍01背包
        }
    }
    cout<<f[V];
    return 0;
}