Description

Input

Output

Sample Input

735 3  4 125  6 5  3 350

633 4  500 30  6 100  1 5  0 1

735 0

0 3  10 100  10 50  10 10

Sample Output

735

630

0

0

Hint

题意是给你几种金钱的面额，每种面额有多少张纸币，然后给一个target金额。问在给定的纸币条件下，能凑成的最大的小于等于target的面额是多少。

关于多重背包，背包九讲里是这么解答处理一件多重背包物品的过程的：

def MultiplePack(F,C,W,M)

	if C * M >= V

		CompletePack(F,C,W)

		return

	k := 1

	while k < M

		ZeroOnePack(kC,kW)

		M := M - k

		k := 2k

	ZeroOnePack(C * M, W * M)

我的理解：首先对于一件物品来说，如果这个物品的容量*数目已经大于背包的总容量了，那么这与完全背包问题没有区别了。因为完全背包问题就是可以任意的往背包里面放物品，而这时这个物品的容量*数目已经大于背包总容量了，所以，也就相当于在背包总容量的范围内，这个物品是可以支持 任意地往背包里面放物品。

如果这个物品的容量*数目小于背包的总容量，那么正常情况下，需要一件一件往里面放找最大值的。但是它的方法是：将第i种物品分成若干件01背包中的物品，其中每件物品有一个系数。这件物品的费用和价值均是原来的费用和价值乘以这个系数。令这些系数分别为1，2, 2的2次方，2的三次方，。。。2的k-1次方，最后是Mi - 2的k次方 + 1，且k是满足Mi - 2的k次方 + 1 的最大整数。例如，如果Mi为13，则相应的k=3，这种最多取13件物品的应被分成系数分别为1
2 4 6 的四件物品。

我觉得这里设计的很nice在于，正常情况下，举例来说这个物品有13件，我们需要一件一件放，放1件，2件，3件，。。。13件都放入，然后不断找最大值。但是上面的方法利用二进制，4个数，就做了13个数的事情。

发现 1 2 4 6 这四个数相互之间的和 就已经可以表示1到13的所有数，原因就在于当我放入1件物品，再放入2件物品找最大值的时候，实际上相当于我一下子放入了该物品的3件，所以实际上3是不需要我们再去实验的了。

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#pragma warning(disable:4996)

using namespace std;

int w, n;

int num[500002];

int val[500002];

int c[500002];

long long dp[500002];

void Zero_Pack(int weight, int cost, int w)

{

	int i;

	for (i = w; i >= cost; i--)

	{

		dp[i] = max(dp[i], dp[i - cost] + weight);

	}

}

void Complete_Pack(int weight,int cost,int w)

{

	int i;

	for (i = cost; i <= w; i++)

	{

		dp[i] = max(dp[i], dp[i - cost] + weight);

	}

}

long long Multi_Pack(int c[],int val[],int num[],int n,int w)

{

	memset(dp, 0, sizeof(dp));

	int i;

	for (i = 1; i <= n; i++)

	{

		if (num[i] * c[i] > w)

			Complete_Pack(val[i],c[i],w);

		else

		{

			int k = 1;

			while (k < num[i])

			{

				Zero_Pack(k*val[i],k*c[i],w);

				num[i] = num[i] - k;

				k = k << 1;

			}

			Zero_Pack(num[i]*val[i],num[i]*c[i],w);

		}

	}

	return dp[w];

}

int main()

{

	int i, j, v, max_v,re;

	while (scanf("%d%d", &n,&w) != EOF)

	{

		memset(dp, 0, sizeof(dp));

		for (i = 1; i <= n; i++)

		{

			scanf("%d%d%d", c + i, val + i, num + i);

		}

		re = Multi_Pack(c, val, num, n, w);

		cout << re << endl;

	}

	return 0;

}