[动态规划]天平

天平

题目描述

Gigel有一个奇怪的天平，他想要使它平衡。事实上，这个东西与其他普通的天平是不同的。
它有两条重量可以忽略的臂，每条臂的长度是15。臂上有一些挂钩，Gigel想要从他拥有的G个重物中（1 <= G <= 20）挂一些上去，这些重物有着不同的重量，重量范围在1到25之间。Gigel可以把任意的重物放到任意的挂钩上，但他必须全部用完所有重物。
最终，Gigel成功地利用他在全国信息学奥赛中的经验将天平弄平衡了。现在他想知道有多少种方式可以让它平衡。
挂钩的位置和重物的重量是已知的，写一个程序来计算能使天平平衡的所有可能数目。
测试样例保证至少有一种能使之平衡的方案。

关于输入

输入由以下组成：
? 第一行包含整数C(2 <= C <= 20)和整数G(2 <= G <= 20);
? 下一行包含C个整数(这些数字也是互不相同的，按递增排序），范围在-15到15之间，代表挂钩的分配；每个数字代表在X轴上相对天平中心的位置（当没有重物在天平上时，天平沿X轴方向平衡。距离的绝对值代表挂钩与天平中心的距离，数字的符号决定挂钩在哪个臂上：负号代表在左臂，正号代表在右臂）
? 再下一行是G个互不相同的自然数，按递增排序，范围在1到25之间，代表重物的重量值。

关于输出

输出包含一个数M，代表使天平平衡的可能方案个数。

例子输入

2 4
-2 3
3 4 5 8

例子输出

2

提示信息

为了与POJ中保持一致，输出结果在可以用int表示的范围内。
使用动态规划。

解题分析

注意，我们要使得天平达到平衡，并且确保每个物品都放上了，所以说，我们可以对每个物品进行枚举，他们分别可以放在不同的钩子上，当我们把全部物品放完之后，就检查一下这个时候天平是不是平衡的，如果是的话，我们就增加方案数，最后输出即可。

#include <iostream>
using namespace std;

int C,G,hook[25],weight[25],ans=0,count=0;

void dfs(int k){
    if(k==G+1){
        if(ans==0) count++;
        return;
    }
    for(int i=1;i<=C;i++){
        ans+=hook[i]*weight[k];
        dfs(k+1);
        ans-=hook[i]*weight[k];
    }
}


int main() {
    scanf("%d%d",&C,&G);
    for(int i=1;i<=C;i++)
        scanf("%d",&hook[i]);
    for(int j=1;j<=G;j++)
        scanf("%d",&weight[j]);
    dfs(1);
    printf("%d\n",count);
	return 0;
}

显然，在小数据范围内，这是有效的，然而，一旦数据达到20 * 20 我们就要枚举20的20次方次！这显然不是一个好的算法！（思路正确但是效率极其低下）。所以，我们考虑采用动态规划去完成本题。

但是我们如何利用动态规划的思想呢？在物品和挂钩有负数的情况下，我们考虑使用一个dp数组dp[i][j]，表示考虑前i个物品，偏移量为j时的方法数，这就很巧妙了，我们很容易得到这样一个递推关系,dp[i][j+weight[i]*hook[m]]+=dp[i-1][j]+1，加一表示我们放了物品i，所以增加了一种方法，用+=是因为我们可以由不同的放置方法达到这个物品数和这个偏移量，所以这样去更新。

并且我们设置dp[0][BALANCE]=1（其中BALANCE我们看做一个较大的常数，用来放置数组下标为负数），表示放0件物品就平衡的方法数为1。

程序首先读取输入，包括挂钩数量C、重物数量G、挂钩位置数组hook[]和重物重量数组weight[]。

然后，定义一个二维数组dp[25][MAXSUM]，其中dp[i][j]表示前i个重物放置在天平上达到平衡状态，使得天平左臂重量减去右臂重量等于j-BALANCE的方案数。BALANCE是一个偏移量，用于保证dp数组的下标不会超出范围。

接下来，程序进行动态规划的过程。首先，将dp[0][BALANCE]设置为1，表示天平上没有放置任何重物时，天平处于平衡状态。然后，遍历所有的重物，对于每个重物，遍历所有的可能状态。

对于第i个重物，如果dp[i-1][j]不为0，表示前i-1个重物放置在天平上达到偏移量为j且方法数已知，那么可以将第i个重物放置在任意一个挂钩上，使得天平左臂重量减去右臂重量的变化量为weight[i]*hook[m]。

最后，程序输出dp[G][BALANCE]，即前G个重物放置在天平上达到平衡状态的方案数。

需要注意的是，为了与题目中保持一致，程序使用BALANCE偏移量来保证dp数组的下标不会超出范围，并且输出结果在可以用int表示的范围内。

代码实现

#include <iostream>
#define BALANCE 25*15*15
#define MAXSUM 2*BALANCE+10
using namespace std;

int C,G,hook[25],weight[25];
int dp[25][MAXSUM];

int main() {
	scanf("%d%d",&C,&G);
	for(int i=1;i<=C;i++){
	    scanf("%d",&hook[i]);
	}
	for(int i=1;i<=G;i++){
	    scanf("%d",&weight[i]);
	}
	dp[0][BALANCE]=1;
	for(int i=1;i<=G;i++)
	    for(int j=1;j<=MAXSUM;j++){
	        if(dp[i-1][j]){
	            for(int m=1;m<=C;m++){
	                dp[i][j+weight[i]*hook[m]]+=dp[i-1][j];
	            }
	        }
	    }
	printf("%d\n",dp[G][BALANCE]);
	return 0;
}