题解 | 【模板】多重背包

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=75e3;
int n,m,T,s[N],w[N],v[N],dp[N],cnt;

void solve(){
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=cnt;i++){
		for(int j=m;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[m]<<endl;
	return;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		int a,b,c,k;
		cnt=0;
		for(int i=1;i<=n;i++){
			cin>>a>>b>>c;
			k=1;
			while(k<=c){
				++cnt;
				w[cnt]=k*a;
				v[cnt]=k*b;
				c-=k;
				k=k*2;
			}
			if(c>0){
				++cnt;
				w[cnt]=c*a;
				v[cnt]=c*b;
			}
		}
		solve();
	}
	
    return 0;
}