POJ - 1837 Balance解题报告

a[i][j]表示把前i个重物都挂上之后，平衡度为j的情况数。g[i]表示第i个物体的重量。d[i]表示第i个挂钩到中心的距离(正负表示左右)。

注意由于这里平衡度有可能出现负数的情况，所有都加上相同的常数，即平移j范围集合[-20*25*15,20*25*15]向右平移7500。 

递推方法：对于第i个重物，枚举它挂在每个挂钩上的情况(枚举j)，a[i][k]+=a[i-1][k-g[i]*d[j]];

边界条件：a[1][g[1]*d[i]]=1;

#include<iostream>#include<math.h>#include<stdio.h>#define P 7500using namespace std;int m,n;int d[30]={0};int g[30]={0};int a[30][2*P+50]={0};int main(){	cin>>m>>n;	for(int i=1;i<=m;i++)	{		scanf("%d",&d[i]);	}	for(int i=1;i<=n;i++)	{		scanf("%d",&g[i]);	}	for(int i=1;i<=m;i++)//确定边界条件 	{		a[1][d[i]*g[1]+P]=1;	}	for(int i=2;i<=n;i++)	{		for(int j=1;j<=m;j++)		{			for(int k=0;k<=2*P;k++)			{				if(k-d[i]*g[j]<0)continue;				a[i][k]+=a[i-1][k-d[j]*g[i]];			}		}	}	cout<<a[n][P];}相比暴力枚举，动态规划少算了的就是，前i-1个重物都挂上之后，i个重物挂在不同的位置，需要再重新枚举前i-1个挂法的重复部分。