多重背包（二进制拆分）

#include<bits/stdc++.h>
using namespace std;
//......此处快读省略........
#define ll long long
int n,m;
int v1[1005],w1[1005],s[20005];
ll v[10005],w[10005];
ll f[20005];
int cnt;
int main(){
    read(n);read(m);

//以下是二进制拆分
    for(int i=1;i<=n;++i){
        read(v1[i]);read(w1[i]);read(s[i]);
        for(int j=1;j<=s[i];j<<=1){
            v[++cnt]=j*v1[i];
            w[cnt]=j*w1[i];
            s[i]-=j;
        }
        if(s[i]>0){
            v[++cnt]=s[i]*v1[i];
            w[cnt]=s[i]*w1[i];
        }
    }
//---------分割线----------//

//以下是01背包模板
    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;
}