题目描述

将01背包,完全背包,多重背包的二进制优化进行整合

#include<iostream>
#include<vector>
using namespace std;
const int N=10010;
int n,m,v[N],s[N],w[N],f[N];
struct goods
{
    int v,w;
};
int main()
{
    cin>>n>>m;
    vector<goods> good;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++) 
    {
        if(s[i]==-1)
        {
            for(int j=m;j>0;j--)
            {
                if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]);
            }
        }
        else if(s[i]==0) 
        {
            for(int j=0;j<=m;j++)
            {
               if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]);
            }
        }
        else
         {
          for(int k=1;k<=s[i];k*=2)
          {
              s[i]-=k;
              good.push_back({k*v[i],k*w[i]});
          }
          if(s[i]>0) good.push_back({s[i]*v[i],s[i]*w[i]});
        } 
    }
    for(auto Good:good)
          {
              for(int j=m;j>0;j--)
              {
                  if(j>=Good.v) f[j]=max(f[j],f[j-Good.v]+Good.w);
              }
          }
    cout<<f[m]<<endl;
    return 0;
}