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\n",max);
		else
			printf("0\n");
	}
	return 0;
}