51nod 1086【背包·DP】

思路：

如果体积乘以数量>=W，那么直接用完全背包模型。如果不到的话，用二进制优化就好了。

基础题，感觉这样写很优雅？回去睡觉。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int dp[50010],n,W;

int c,w,v;

void zero_or_one(int val,int wi)

{

	for(int i=W;i>=wi;i--)

		dp[i]=max(dp[i],dp[i-wi]+val);

}

void complete(int val,int wi)

{

	for(int i=wi;i<=W;i++)

		dp[i]=max(dp[i],dp[i-wi]+val);

}

int main()

{

	int k;

	scanf("%d%d",&n,&W);

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

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

	{

		scanf("%d%d%d",&w,&v,&c);

		if(c*w>=W)

			complete(v,w);

		else

		{

			k=1;

			while(k<c)

			{

				int ww=w*k;

				int vv=v*k;

				zero_or_one(vv,ww);

				c-=k;

				k<<=1;

			}

			k=c;

			int ww=w*k;

			int vv=v*k;

			zero_or_one(vv,ww);

		}

	}

	printf("%d\n",dp[W]);

	return 0;

}

巴特西

51nod 1086【背包·DP】

最新文章

热门文章