（POJ1837）Balance 01背包变形经典题

本文主要是介绍（POJ1837）Balance 01背包变形经典题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Balance
Description

Gigel has a strange “balance” and he wants to poise it. Actually, the device is different from any other ordinary balance.
It orders two arms of negligible weight and each arm’s length is 15. Some hooks are attached to these arms and Gigel wants to hang up some weights from his collection of G weights (1 <= G <= 20) knowing that these weights have distinct values in the range 1..25. Gigel may droop any weight of any hook but he is forced to use all the weights.
Finally, Gigel managed to balance the device using the experience he gained at the National Olympiad in Informatics. Now he would like to know in how many ways the device can be balanced.

Knowing the repartition of the hooks and the set of the weights write a program that calculates the number of possibilities to balance the device.
It is guaranteed that will exist at least one solution for each test case at the evaluation.
Input

The input has the following structure:
• the first line contains the number C (2 <= C <= 20) and the number G (2 <= G <= 20);
• the next line contains C integer numbers (these numbers are also distinct and sorted in ascending order) in the range -15..15 representing the repartition of the hooks; each number represents the position relative to the center of the balance on the X axis (when no weights are attached the device is balanced and lined up to the X axis; the absolute value of the distances represents the distance between the hook and the balance center and the sign of the numbers determines the arm of the balance to which the hook is attached: ‘-’ for the left arm and ‘+’ for the right arm);
• on the next line there are G natural, distinct and sorted in ascending order numbers in the range 1..25 representing the weights’ values.
Output

The output contains the number M representing the number of possibilities to poise the balance.
Sample Input

2 4
-2 3
3 4 5 8
Sample Output

2
Source

Romania OI 2002

题意：
有一个device（直杆），以中点为支点，左右长度都为15，上面在不同位置分布着一些挂钩。现在给出c个挂钩，和它们在杆上的位置（以中点的原点的x轴表示），以及Gigel有G个砝码，和它们各自的重量。求如果把这些钩码全部挂在任意钩上（一钩个挂任意多个），最终device能达到平衡的情况数。

分析：
这是一题杠杆原理的物理题，要使杠杆平衡这左边的负力矩等于右边的正力矩。即所有的力矩之和为0.
所以我们要求的是：将所有的砝码放上去后力矩和为0的方案数？
每个砝码可以放置在任意的位置上，只要最后力矩和为0即可。那么我们就要枚举出所有的情况，然后看最后和为0的方案有多少。
力矩有负数的情况所以为了方便表示，我们将所有的情况向右移7500位，力矩和的范围[0,15000].就变成了一道类似01背包的问题了。
dp[i][j]表示放了前i个砝码后，力矩和为j的方案数。
所以状态转移方程： dp[i][j + w[i]*h[k] ] += dp[i][j]
初始化：刚开始是平衡的所以 dp[0][7500] = 1;

AC 代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;int h[25],w[25];
int dp[25][15010];
int C,G;int main()
{while(scanf("%d%d",&C,&G)!=EOF){for(int i=0;i<C;i++)scanf("%d",&h[i]);for(int i=1;i<=G;i++)scanf("%d",&w[i]);memset(dp,0,sizeof(dp));dp[0][7500] = 1;for(int i=1;i<=G;i++){for(int j=0;j<=15000;j++){if(dp[i-1][j]){for(int k=0;k<C;k++)dp[i][j+w[i]*h[k]] += dp[i-1][j];}}}printf("%d\n",dp[G][7500]);}return 0;
}