题目描述

有 N 种物品和一个容量是 V 的背包。

物品一共有三类：

第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

样例

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

算法1
直接就是把三种物品按模板弄好，能使多次的物品用二进制优化变成多个不同物品，循环时若s[i]为0，则第二重循环用完全背包解法，若s[i]为-1，则第二重循环用01背包解法。
纯暴力

#include<iostream>
#include<cstring>

using namespace std;
const int N=1000010;
int v[N],w[N],s[N],cnt;
int f[N];

int main()
{
    int n,m;
    cin>>n>>m;
    memset(s,-1,sizeof s);
    for(int i=0;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(c>1)
        {
           int k=1;
           while(k<=c)
          {
            v[++cnt]=k*a;
            w[cnt]=k*b;
            c-=k;
            k*=2;
          }
          if(c>0)
          {
            v[++cnt]=c*a;
            w[cnt]=c*b;
          }
        }
        else
        {
            v[++cnt]=a;
            w[cnt]=b;
            if(c==0) s[cnt]=0;
        }
    }


    for(int i=1;i<=cnt;i++)
    {
        if(s[i]==-1)
        {
            for(int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
        else
        {
            for(int j=v[i];j<=m;j++)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }

    cout<<f[m];
    return 0;
}

算法2
在1的基础之上，可以把无限使用的物品用背包总容量限制成有限个，再用多重背包二进制优化，这样不需要再循环中判断是否是无限使用物品，直接变成01背包问题

#include<iostream>
#include<cstring>

using namespace std;
const int N=10010;
int v[N],w[N],cnt;
int f[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(c==0) c=m/a;
        else if(c==-1) c=1;
        if(c>1)
        {
           int k=1;
           while(k<=c)
          {
            v[++cnt]=k*a;
            w[cnt]=k*b;
            c-=k;
            k*=2;
          }
          if(c>0)
          {
            v[++cnt]=c*a;
            w[cnt]=c*b;
          }
        }
        else
        {
            v[++cnt]=a;
            w[cnt]=b;
        }
    }

    for(int i=1;i<=cnt;i++)
    {
        {
            for(int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }

    cout<<f[m];
    return 0;