多重背包

多重背包问题通常可转化成01背包问题求解。但若将每种物品的数量拆分成多个1的话，时间复杂度会很高，从而导致TLE。所以，需要利用二进制优化思想。即：
一个正整数n，可以被分解成1,2,4,…,2^(k-1), n-2^k+1 的形式。其中，k是满足n-2^k+1>0的最大整数。
例如，假设给定价值为2，数量为10的物品，依据二进制优化思想可将10分解为1+2+4+3，则原来价值为2，数量为10的物品可等效转化为价值分别为 1 * 2, 2 * 2, 4 * 2, 3 * 2, 即价值分别为2，4，8，6，数量均为1的物品。

#include
#include
#pragma warning(disable:4996)
using namespace std;

int M, n, vv, mm, ss, a, b, v[10005], m[10005], dp[40005];

int main()
{
	//freopen("D:\\oj_sample\\baowu\\2.in", "r", stdin);
	scanf("%d %d", &n, &M);
	for (int i = 0; i < n; i++)
	{
		scanf("%d %d %d", &vv, &mm, &ss);
		for (int j = 1; j <= ss; j <<= 1)
		{
			v[a++] = vv * j;
			m[b++] = mm * j;
			ss -= j;
		}
		if (ss) v[a++] = vv * ss, m[b++] = mm * ss;
		/*if (ss) v[a++] = vv * ss; m[b++] = mm * ss;*/
	}
	for (int i = 0; i < a; i++)
	{
		for (int j = M; j >= m[i]; j--)
		{
			dp[j] = max(dp[j], dp[j - m[i]] + v[i]);
		}
	}
	printf("%d\n", dp[M]);
	return 0;
}