poj 1837 Balance (01背包)

题意：有一个两臂长15的天平上有n个钩子，现在有g个不同质量砝码。

用上所有的砝码使天平平衡有多少种方法。

分析：关键在于怎么样选择状态才好表示状态转移。

dp[i+w[i]*pos[k]]][j]表示用了i个砝码达到平衡度为j有多少种方法。

dp[i+w[i]*pos[k]][j]=sum(dp[i-1][j])  

由于距离c[i]的范围是-15~15，钩码重量的范围是1~25，钩码数量最大是20

因此最极端的平衡度是所有物体都挂在最远端，因此平衡度最大值为j=15*20*25=7500。原则上就应该有dp[ 1~20 ][-7500 ~ 7500 ]。

因此为了不让下标出现负数，做一个处理，使使得数组开为 dp[1~20][0~15000]，则当j=7500时天枰为平衡状态

具体分析请参见：http://blog.csdn.net/lyy289065406/article/details/6648094

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

int dp[25][15005];
int w[25],pos[25];

int main()
{
    int n,g;
    while(scanf("%d%d",&n,&g)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&pos[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]) continue;   //如果这个状态还未统计方法数
                for(int k=1;k<=n;k++)       //选择一个位置
                    dp[i][j+pos[k]*w[i]]+=dp[i-1][j];
            }
        }
        printf("%d\n",dp[g][7500]);
    }
    return 0;
}

poj 1837 Balance (01背包)

原文：http://blog.csdn.net/u012841845/article/details/18845377