题目链接：
https://cn.vjudge.net/problem/POJ-1837
题目大意：
一个天平上有C个挂钩，第i个挂钩的位置为C[i]，C[i] < 0表示该挂钩在原点的左边，C[i] > 0表示该挂钩在原点的右边；然后给出G个钩码的重量，问有多少种挂法使得天平保持平衡。
解题思路：
分析：当天平平衡时，每向天平上挂一个钩码，天平的状态就会改变，而这个状态可以由若干前一状态获得。
首先定义一个平衡度j的概念
当平衡度j=0时，说明天枰达到平衡，j>0，说明天枰倾向右边（x轴右半轴），j<0则相反
那么此时可以把平衡度j看做衡量当前天枰状态的一个值
因此可以定义一个 状态数组dp[i][j]，意为在挂满前i个钩码时，平衡度为j的挂法的数量。
由于距离L[i]的范围是-15~15，钩码重量的范围是w[i]是1~25，钩码数量最大是20
因此最极端的平衡度是所有物体都挂在最远端，因此平衡度最大值为j=15*20*25=7500。原则上就应该有dp[ 1~20 ][-7500 ~ 7500 ]。
因此为了不让下标出现负数，做一个处理，使得数组开为 dp[1~20][0~15000]，令7500对应0，则当j=7500时天枰为平衡状态。
代码中设置10000为平衡状态
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #include<stack> 8 #include<map> 9 #include<sstream> 10 #define Mem(a, b) memset(a, b, sizeof(a)) 11 using namespace std; 12 typedef long long ll; 13 int dp[21][20005]; 14 //dp[i][j]表示前i个物品平衡度为j的状态的种数 15 //由于左端平衡度小于0，右端大于0，所以全部偏移10000即可(因为最大平衡度只有7500) 16 int l[21], w[21]; 17 int main() 18 { 19 int n, m; 20 scanf("%d%d", &n, &m); 21 for(int i = 1; i <= n; i++)scanf("%d", &l[i]); 22 for(int i = 1; i <= m; i++)scanf("%d", &w[i]); 23 dp[0][10000] = 1;//初始化设置平衡度为10000时，两端平衡，前0个物品使得两端平衡的情况有1种，即两端都不放 24 for(int i = 1; i <= m; i++)//枚举第i件物品 25 { 26 for(int j = 1; j <= 20000; j++)//枚举每一个状态 27 if(dp[i - 1][j])//如果dp[i - 1][j]不为0，状态可以转移 28 { 29 for(int k = 1; k <= n; k++)//枚举钩子，也就是每个物品的不同平衡度的时候放置每个钩子上 30 dp[i][j + l[k] * w[i]] += dp[i - 1][j]; 31 } 32 } 33 cout<<dp[m][10000]<<endl; 34 return 0; 35 }