前言：好久没有写分组背包了，写一个二进制优化的背包练练手

---

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;#define int long long 
int n,w;
const int N = (int)1e7;
struct node{int value,weight;
}sto[N];
int dp[40004];signed main(){cin >> n >> w;int idx = 0;for(int i=1;i<=n;i++){int x,y,z; cin >> x >> y >> z;int c = 1;while(z>c){sto[++idx].value = x * c;sto[idx].weight = y * c;z -= c;c <<= 1; }sto[++idx].value = x * z;sto[idx].weight = y * z;}for(int i=1;i<=idx;i++){for(int j=w;j>=sto[i].weight;j--){dp[j] = max(dp[j],dp[j-sto[i].weight]+sto[i].value );}}cout << dp[w];return 0;
}