题意

• 种物品，每种物品有 个，体积 ，价值 ，背包体积 ，求最大价值

思路

• 可以把每个物品直接放 次，转化为01背包，大数据会TLE
• 打包-二进制优化：显然，每个数n可以拆成所有不大于它的二进制次方组合+剩余部分，如此便可表示从0~n，所以对每个 进行拆分，从1开始，不断拆分，直到拆不出来，就把剩下的打包为一堆，优化后仍然是一个01背包

AC代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define se second
#define fi first
using namespace std;

int dp[202020];
int x[200],vol[200],val[200];
vector<pii> vv;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    int n,T;
    cin >> n >> T ;
    for(int i=1;i<=n;i++){
        cin >> x[i] >> vol[i] >> val[i] ;
    }
    
    //pack
    vv.push_back({0,0});
    for(int i=1;i<=n;i++){
        int tp=1;
        while(x[i]-tp>=0){
            x[i]-=tp;
            vv.push_back({tp*vol[i],tp*val[i]});
            tp<<=1;
        }
        if(x[i]) vv.push_back({x[i]*vol[i],x[i]*val[i]});
    }

    int sz=vv.size();
    for(int i=1;i<sz;i++){
        for(int j=T;j>=vv[i].fi;j--){
            dp[j]=max(dp[j],dp[j-vv[i].fi]+vv[i].se);
        }
    }
    cout << dp[T] << endl ;
    return 0;
}