多重背包与二进制优化

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxm = 100005;
ll v[maxm], w[maxm], cnt[maxm];
ll dp[maxm];
ll weight, value, cnt;
int main(){
    cnts = m;
    for(int i = 1; i <= m; i++){
        scanf("%lld%lld%lld", &v[i], &w[i], &cnt[i]);
    }
    memset(dp, 0xc0, sizeof(dp));  //初始化
    dp[0] = 0;
    for(ll i = 1; i <= m; i++){
        for(ll j = 1; cnt[i] >= j; j <<= 1){
            ++cnts;
            v[cnts] = 1ll * v[i] * j;
            w[cnts] = 1ll * w[i] * j;
            cnt[i] -= j;
        }
        v[i] = 1ll * v[i] * cnt[i], w[i] = 1ll * w[i] * cnt[i];
    }
    for(ll i = 1; i <= cnts; i++){
        for(ll j = weight; j >= w[i]; j--){
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
    }
}