POJ 1837Balance(动态规划 好题)

给一个天平，然后有许多砝码，问把砝码加上去达到平衡状态的方案数。

测试用例分析：

2 4                   代表有在天平上有两个钩子，砝码有四种

-2 3                  钩子的位置，负数代表在左边，正数代表在右边

3 4 5 8             分别给出四种砝码的重量

什么时候达到平衡呢？就是臂力=臂长*重量，当两边的臂力相等的时候就会平衡了。

题目说的意思是所有的砝码都要用到，我们先分析一下样例。

取第一个砝码 -6 9

取第二个砝码 -14 6 1 21

取第三个砝码 -24 1 -4 21 -9 16 11 36

取第四个砝码 -40 0 0 40

由于第四行太多，没有全部列举，可以看出来，共有两种方案。我们可以使用动态规划的思想，从上层往下层递推。

为了避免负数的出现，我们分析数据g*pos*wei<=20*15*25=7500那么范围就是-7500~7500，那么我们可以使用

dp[25][1500]的背包装这些砝码，状态转移方程为dp[i][j+pos[k]*wei[i]]+=dp[i-1][j];

当然首先得初始化dp[0][7500]=0，标志未放砝码时,7500位置为平衡点。

最后的答案即为dp[g][7500]。

题目地址：Balance

看了几小时，终于看懂了。。哭。

AC代码：

#include<iostream>
#include<cstring>
using namespace std;

int dp[25][15001];
int pos[25],wei[25];

int main()
{
    int c,g;
    int i,j,k;

    while(cin>>c>>g)
    {
        for(i=1; i<=c; i++)
            cin>>pos[i];
        for(i=1; i<=g; i++)
            cin>>wei[i];

        memset(dp,0,sizeof(dp));
        dp[0][7500]=1;    //一个砝码也不挂

        for(i=1; i<=g; i++)   //g个砝码
            for(j=0; j<=15000; j++)
                if(dp[i-1][j])  //说明可以在往上面挂
                    for(k=1; k<=c; k++)   //c个位置
                        dp[i][j+wei[i]*pos[k]]+=dp[i-1][j];

        cout<<dp[g][7500]<<endl;
    }
    return 0;
}

/*
2 2
-1 1
2 2
2 3
-1 1
2 3 5
*/