poj 1837DP 问题

题意：在平衡秤上，左右分别有n个固定点，给你m个重量的秤砣，要求你把这些秤砣全部用上并保持平衡，求这样的组合有多少？

 

 

思路：这个题我做的时候是归类在0-1背包里，然后这题又不是常规的求最优解，所以可以联想到给出若干物品  求其能组合的类型有多少这类类型的题目，分析知它最大的值为20*15*25=7500，然后乘上20=15000。明显可以用数组装下。所以可以这样定义它的状态：dp[i][j]《i为（1，m），j为（-7500,7500）》即在用第i个秤砣的时候，在力矩为j的位置的组合数，然后其初始状态为d[0][7500]=1，即什么都不放时在平衡点的组合数为1；
其实数组书可以只用开到7500，因为超过3750就没必要继续保存即这种条件下已经不能回到平横状态了。

关于状态转移方程的问题：一开始很难想到怎么样记录状态，但是我们发现要求的是平衡的种类数，因此我们可以想到的是dp数组保存的是平衡时候的种类数，但是我们为了想到一个比较好的能够保存状态并且展现最终的种类数的记录状态的方式，于是我们尝试使用dp[i][j]表示使用使用了前i个物品时，使得天平左右相差为j的时候的种类数。于是我们很容易得到状态转移方程，dp[i]可以由dp[i-1]的一个值，放第i个物品在挂钩某个位置，转移到dp[i][j],dp[i][j]就是所有这些满足合法条件的dp[i-1]的总和

#include <iostream>
using namespace std;
const int mMax=22;
const int nMax=15000;
const int temp=7500;

int hoo[mMax],wei[mMax];
int dp[mMax][nMax];

int main()
{
	int i,j,c,g,v,val;
	while (scanf("%d%d",&c,&g)!=EOF)
	{
		for (i=1;i<=c;i++)
			cin>>hoo[i];
		for (j=1;j<=g;j++)
			cin>>wei[j];
		memset(dp,0,sizeof(dp));
		dp[0][temp]=1;
		for (i=1;i<=g;i++)
			for (j=1;j<=c;j++)
			{
				val=wei[i]*hoo[j];
				for (v=0;v<=nMax;v++)
					if (dp[i-1][v]!=0)
						dp[i][val+v]+=dp[i-1][v];//状态转移方程
			}
			cout<<dp[g][temp]<<endl;
	}
	return 0;
}

 

 

 

其实这道题目并不能算严格意义上的DP或者0/1背包问题，至于动态规划与0/1背包问题，将在以后会深入学习并加以理解。