这题在网上搜解题报告不理想。写的都很搓。导致我独自背了一个下午的背包。

这题就是普通的0-1背包问题。

难点就在于变形。

我用点数来刷背包ＤＰ 容量即为总点数sum 物品容量则是 每次对换点数之差为g

I问题就在于g的值有正负，所以刷背包时要注意数组下标多加10000左右，即0表示为10000。这样处理正负比较容易。还要说的是因为Q正负的缘故，我把刷背包分为两段，正负分开。

II问题出现在最后查找最小值的时候。逻辑要清晰。

代码如下。 比搜索结果里的博客写的好哇。^^自我陶醉。

#include <iostream>
#define S 10000
using namespace std;
int dp[16100];

int ABS(int n)
{
	if(n<0)
		return -n;
	else
		return n;
}

int main()
{
	int n,i,g,j,sum,k,ans,t,f;
	int o[1100],p[1100],min;
	while(cin>>n)
	{
		sum=0;
		k=0;
		for(i=1;i<=n;i++)
		{
			cin>>o[i]>>p[i];
			sum+=o[i]+p[i];
			k+=o[i];
		}
		k=k+S;
		t=k;
		for(i=0;i<=sum+S;i++)
			dp[i]=999999;
		dp[k]=0;
		for(i=1;i<=n;i++)
		{
			g=p[i]-o[i];
			if(g<0)
			{
				for(j=S-g;j<=sum+S;j++)
					if(dp[j+g]>dp[j]+1)
						dp[j+g]=dp[j]+1;
			}
			else
			{
				for(j=S+sum;j>=S+g;j--)
	    			if(dp[j-g]+1<dp[j])
		    			  dp[j]=dp[j-g]+1;
			}
		}
		ans=999999;
		min=999999;
    	        for(i=S;i<=S+sum;i++)
		{
			if(dp[i]!=999999)
			{
				if(min>ABS(sum-2*(i-S)))
				{
					ans=dp[i];
					min=ABS(sum-2*(i-S));
				}
				else if(min==ABS(sum-2*(i-S)))
				{
					if(ans>dp[i])
						ans=dp[i];
				}
			}
		}
		cout<<ans<<endl;
	}


	return 0;
}

• 好像S没必要吧 (9) lead_my_life 2011-01-22 13:28:00