多重背包模板

二进制优化

#include<bits/stdc++.h>
using namespace std;
int n,V,k;
int w[110],v[110],m[110],nw[1110],nv[1110];
int dp[100010];
int main(){
    cin>>n>>V;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i]>>m[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m[i];j*=2){
            m[i]-=j;
            nw[++k]=w[i]*j;
            nv[k]=v[i]*j;
        }
        if(m[i]){
            nw[++k]=w[i]*m[i];
            nv[k]=v[i]*m[i];
        }
    }
    for(int i=1;i<=k;i++){
        for(int j=V;j>=nw[i];j--){
            dp[j]=max(dp[j],dp[j-nw[i]]+nv[i]);
        }
    }
    cout<<dp[V];
}