有N種物品，每種物品的數(shù)量為C1，C2......Cn。從中任選若干件放在容量為W的背包里，每種物品的體積為W1，W2......Wn（Wi為整數(shù)），與之相對應(yīng)的價值為P1,P2......Pn（Pi為整數(shù)）。求背包能夠容納的最大價值。

我們可以轉(zhuǎn)化成01背包來做，但是這樣很慢。

所以我們可以二進制優(yōu)化。

一個數(shù)a，我們可以按照二進制來分解為1 + 2 + 4 + 8 …… +2^n + 剩下的數(shù) = a

剩下的數(shù)等于a - (1 + 2 + 4 + 8 …… +2^n )

我們把a拆成這么多項，可以證明，這么多項可以組合出1~a的每一個數(shù)

所以我們就可以把數(shù)量拆分，分成一些物品。這樣會快很多。

#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;

const int MAXN = 112;
const int MAXM = 51234;
int f[MAXM], v[MAXN * 10], w[MAXN * 10];
int n, m, N;

void add(int ww, int vv, int cc) //拆分 
{
	int now = 1;
	while(1)
	{
		if(cc <= now)
		{
			w[N] = ww * cc;
			v[N++] = vv * cc;
			break;
		}
		else cc -= now;
		w[N] = ww * now;
		v[N++] = vv * now;
		now <<= 1;
	} 
}

int main()
{
	scanf("%d%d", &n, &m);
	REP(i, 0, n)
	{
		int ww, vv, cc;
		scanf("%d%d%d", &ww, &vv, &cc);
		add(ww, vv, cc);
	}
	REP(i, 0, N)
		for(int j = m; j >= w[i]; j--)
			f[j] = max(f[j], f[j - w[i]] + v[i]);
	printf("%d\n", f[m]);
	return 0;	
} 

?

?