朴素做法

会超时

C++ 代码

#include <iostream>

using namespace std;

const int N=1010;

int v[N],w[N],s[N];
int f[N][N];
int n,m;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];

    for(int i=1;i<=n;i++){
      for(int j=0;j<=m;j++){

        if(s[i]==-1){  // 01背包
            f[i][j]=f[i-1][j];
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
        else if(s[i]==0){  // 完全背包
           f[i][j]=f[i-1][j];
           if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);  
        }
        else {  // 多重背包
            for(int k=0;k<=s[i]&&j>=k*v[i];k++)
             f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
        } 

      }
    }

    cout<<f[n][m]<<endl;

    return 0;
}

优化做法1

把01背包和完全背包转化为 多重背包
再将多重背包二进制优化为 01背包

Code

#include <iostream>

using namespace std;

const int N=10010;

int v[N],w[N],s[N];
int f[N];
int n,m;

int main(){
    cin>>n>>m;
    int t=1;
    for(int i=1;i<=n;i++) {
      int vi,wi,si;
      cin>>vi>>wi>>si;  
      if(si==-1)  si=1;         // 把01背包转化为 多重背包
      else if(si==0) si=m/vi;   // 把完全背包转化为 多重背包


      // 下面是把多重背包二进制优化转换为 01背包  
      int k=1; 
      while(si>=k){
           v[t]=vi*k;
           w[t++]=wi*k;
           si-=k;
           k*=2;   
       }
       if(si>0) v[t]=vi*si,w[t++]=wi*si;
    }

    n=t-1;
    for(int i=1;i<=n;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;
}

优化做法2

把多重背包转化为01背包

Code

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=10010;

struct node{
    int kind;
    int v,w;
};
vector<node>p;
int n,m;
int f[N];

int main(){         //把多重背包转化为  01背包

    cin>>n>>m;

    for(int i=1;i<=n;i++) {
        int vi,wi,si;
        cin>>vi>>wi>>si;
        if(si==-1)  p.push_back({-1,vi,wi});         // 01背包
        else if(si==0)  p.push_back({0,vi,wi});         // 完全背包
        else{ // 多重背包
            int k=1;
            while(si>=k){
                p.push_back({-1,vi*k,wi*k});
                si-=k;
                k*=2;
            }
           if(si) p.push_back({-1,vi*si,wi*si});
       }

    }

    for(int i=0;i<p.size();i++){
        node p1=p[i];
        if(p1.kind==-1)
          for(int j=m;j>=p1.v;j--)
            f[j]=max(f[j],f[j-p1.v]+p1.w);

        else
          for(int j=p1.v;j<=m;j++)
           f[j]=max(f[j],f[j-p1.v]+p1.w);
    }

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