题解 | 【模板】多重背包

#include <iostream>
#include <vector>
using namespace std;

int main() {
   int t;
   cin>>t;
   while(t--)
   {
    int n,m;
    cin>>n>>m;

    vector<int> w(n+1);
    vector<int> v(n+1);
    vector<int> s(n+1);

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

    vector<long> dp(m+1,0);

    for(int i=1;i<=n;i++)
    {
        int num=s[i];
        for(int k=1;num>0;k<<=1)
        {
            int count=min(k,num);
            num-=count;

            for(int j=m;j>=w[i]*count;j--)
            {
                dp[j]=max(dp[j],dp[j-w[i]*count]+v[i]*count);
            }

        }
    }
    cout<<dp[m]<<endl;
   }
   return 0;
}
// 64 位输出请用 printf("%lld")