POJ1837-Balance

题目链接：https://vjudge.net/problem/POJ-1837

题意：给你一根杠杆，轴在中心标记位0，中心左边，从左到右标记-15,-14,…,-1,中心右端，1，2，3,…,15，表示到中心的距离。现在给你c个挂钩，g个砝码。告诉你挂钩位置和每个砝码的重量，要求用完所有砝码。问：使得杠杆平衡的方案数是多少？

思路：动态规划。首先定义平衡度 b a l a n c e = Σ w [ i ] ∗ c [ k ] balance=Σw[i]*c[k] balance=Σw[i]∗c[k],w是砝码重量，c是砝码位置，显然当balance=0时，杠杆是平衡的。balance>0右端低，balance<0左端低。

定义： d p [ i ] [ j ] dp[i][j] dp[i][j]表示使用前i个砝码时，平衡度达到j时杠杆平衡的方案数。

放了i-1个砝码，平衡度为j时，状态为dp[i-1][j].

现在放第i个砝码：平衡度变为 j→j+w[i]*c[k].

此时放了i个砝码，平衡度为j+w[i]*c[k],状态为dp[i][j+w[i]*c[k]].

因为，末状态dp[i][j+w[i]*c[k]]可能由多个初状态得到所以要对dp[i-1][j]求和，不难得到

状态转移方程：

dp[i][j+w[i]*c[k]]=Σdp[i-1][j].

规划方向：采用自顶向下的方式。来求dp。循环变量及顺序（由外到内）:j->w->c

目标答案：dp[cnt_w][7500]。（砝码用完时的平衡方案数）

代码：

#include<iostream>
using namespace std;
const int maxn=27;
int dp[maxn][15001];
int w[maxn];
int c[maxn];
 
int main(){
	int n_c,n_w;
	cin>>n_c>>n_w;
	int i;
	for(i=1;i<=n_c;i++)cin>>c[i];
	for(i=1;i<=n_w;i++)cin>>w[i];
	dp[0][7500]=1;
	int j,k;
		for(i=1;i<=n_w;i++){
			for(j=0;j<=15000;j++){
			for(k=1;k<=n_c;k++){
				if(j+w[i]*c[k]>=0)dp[i][j+w[i]*c[k]]+=dp[i-1][j];
			}
		}
	}
	cout<<dp[n_w][7500]<<endl;
	return 0;
} 

动态规划过程：

1.相关变量(如本题的w，c，平衡度，方案数)

2.定义dp(一维还是两维？dp i j的意思？)

3.暴力枚举简单解，确定状态转移方程

4.确定规划方向 ↑还是↓

5.目标答案的表达（放到第三步也行）