5. 多重背包问题 II - AcWing题库

#include <bits/stdc++.h>
using namespace std;
const int MAXN=11050;       //个数是1000*log2(2000)；1000×以log以2为底2000的数
const int MAXV=2005;
int temp_v[MAXN];       //存储实际每个的体积
int temp_w[MAXN];       //存储实际每个的价值
int v[MAXN];            //要拓展的体积
int w[MAXN];            //要拓展的个数
int s[MAXN];            //存储件数
int dp[MAXV];
int vi;
int n;
void knapsack()
{for(int i=1;i<=n;i++){for(int j=vi;j>=v[i];j--){dp[j]=max(dp[j],dp[j-v[i]]+w[i]);   //01背包的滚动数组}}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>vi;for(int i=1;i<=n;i++){cin>>temp_v[i]>>temp_w[i]>>s[i];}int k=0;        //要拓展的下标for(int i=1;i<=n;i++){for(int j=1;j<=s[i];j<<=1){k++;            //下标加1 v[k]=j*temp_v[i];w[k]=j*temp_w[i];s[i]-=j;}if(s[i]!=0){k++;        //下标加1 v[k]=s[i]*temp_v[i];w[k]=s[i]*temp_w[i];}}n=k;knapsack();cout<<dp[vi]<<'\n';	return 0;}