处理多重背包_二进制拆分优化（难度：***）

#include <bits/stdc++.h>
#define ios                               \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);                     \
    cout.tie(nullptr)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define lowbit(x)  ((x) & - (x))
#define pb push_back
#define SZ(v) ((int)v.size())
#define PI acos(-1)
#define x first
#define y second
#define mem(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f; 
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-6;
const int MAX=2e5+10;
const ll mod=1e9+7;
/********************************* std-head *********************************/
const int N=1e5+10;
int n,C,dp[N];
int w[N],c[N],m[N];
int new_n;           //二进制拆分后的新物品的总数量 
int new_w[N],new_c[N],new_m[N];  //二进制拆分后的新物品
int main(){
	ios;
	cin>>n>>C;
	rep(i,1,n) cin>>w[i]>>c[i]>>m[i];
//以下为二进制拆分的思想
    int new_n=0;
	rep(i,1,n){
		for(int j=1;j<=m[i];j<<=1)  //二进制枚举：1,2,4... 
		{
			m[i]-=j;       //减去已拆分的，算剩下需要拆分的值 
			new_c[++new_n]=j*c[i];
			new_w[new_n] = j*w[i];
			
		}
		if(m[i]){   // 最后一个数是余数 
			new_c[++new_n]=m[i]*c[i];
			new_w[new_n]=m[i]*w[i];
		}
	}	
//一下是滚动数组版本的0/1背包
	rep(i,1,new_n)   //枚举物品 
	per(j,new_c[i],C) //枚举背包容量 
	dp[j]=max(dp[j],dp[j-new_c[i]]+new_w[i]);
	cout<<dp[C]<<endl; 
	
	
	return 0;
}