题意简述

给你$n$个物品，第$i$个物品的体积为$w_i$,价值为$v_i$,可以选$m_i$次。现在你可以选的物品总体积不超过$W$，求你能获得的最大的价值

解题思路

感觉把多重背包的问题模型重温了一遍有没有……
由于数据范围很大，所以我们直接将选$m$次拆成有$m$个物品可选这个暴力的方案是会超时的，所以我们要用二进制分解去优化多重背包。
我们用$W_{i,j}$表示为由$2^j$个物品$i$捆绑而成的大物品。若$m$不是$2$的整数次幂，那么我们应将物品$i$进行二进制分解以后剩下的选取次数捆绑成一个大物品并单独储存。二进制分解完成后，我们再跑朴素的0/1背包求解即可。

code

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register
#define qwq printf("qwq\n");

using namespace std;

int read()
{
	register int x = 0,f = 1;register char ch;
	ch = getchar();
	while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
	while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
	return x * f;
}

int n,f[100005],ans,cnt,m,w[100005],v[100005],W,V,t;

int main()
{
	n = read(); t = read();
	for(int i = 1; i <= n; i++)
	{
		V = read();
		W = read();
		m = read();
		for(int j = 1; j <= m; j <<= 1)
		{
			w[++cnt] = W * j;
			v[cnt] = V * j;
			m -= j;
		}
		if(m) w[++cnt] = W * m,v[cnt] = V * m;
	}

	for(int i = 1; i <= cnt; i++)
		for(int j = t; j >= w[i]; j--)
			f[j] = max(f[j],f[j - w[i]] + v[i]);
	cout << f[t];
    return 0;
}