51nod 1086 背包问题 V2

#include <bits/stdc++.h>
using namespace std;

long long dp[2][50050],cost[110],val[110],num[110],c[770],v[770];

int main()
{
	long long n,w,i,j,x,cnt;
	while(cin>>n>>w)
	{
		for(i=1;i<=n;i++)
			scanf("%lld%lld%lld",&cost[i],&val[i],&num[i]);
		cnt=1;
		for(i=1;i<=n;i++)
		{
			x=1;
			while(x<=num[i])
			{
				c[cnt]=cost[i]*x;
				v[cnt]=val[i]*x;
				cnt++;
				num[i]-=x;
				x<<=1;
			}
			if(num[i])
			{
				c[cnt]=cost[i]*num[i];
				v[cnt]=val[i]*num[i];
				cnt++;
			}
		}
		memset(dp,0,sizeof(dp));
		for(i=1;i<cnt;i++)
		{
			for(j=1;j<=w;j++)
			{
				if(j<c[i])
					dp[i&1][j]=dp[i&1^1][j];
				else
					dp[i&1][j]=max(dp[i&1^1][j],dp[i&1^1][j-c[i]]+v[i]);
			}
		} 
		printf("%lld\n",dp[cnt&1^1][w]);
	}
}