poj 2184 Cow Exhibition（背包变形）

这道题目和抢银行那个题目有点儿像，同样涉及到包和物品的转换。

我们将奶牛的两种属性中的一种当作价值，另一种当作花费。把总的价值当作包。然后对于每一头奶牛进行一次01背包的筛选操作就行了。

需要特别注意的是，当x小于0的时候，循环应该是正向的，不明白的话，好好想想01背包的一维解法为什么是逆向的。

#include<stdio.h>
#include<string.h>
#define MAX 99999999
#define N 201005
int dp[N];
int Max(int x,int y)
{
	if(x>y)
		return x;
	else
		return y;
}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int i;
		for(i=0;i<N;i++)
			dp[i]=-MAX;
		dp[100000]=0;
		while(n--)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			if(x<0&&y<0)
				continue;
			else if(x>0)
			{
				for(i=200000;i>=x;i--)
					dp[i]=Max(dp[i],dp[i-x]+y);
			}
			else
			{
				for(i=0;i<=200000+x;i++)
					dp[i]=Max(dp[i],dp[i-x]+y);
			}
		}
		int max=-MAX;
		for(i=200000;i>=100000;i--)
		{
			if(dp[i]>=0)
				max=Max(max,dp[i]+i-100000);
		}
		if(max>0)
			printf("%d
",max);
		else
			printf("0
");
	}
	return 0;
}