- POJ 1837 - Balance
- Time: 1000MS
- Memory: 30000K
- 难度: 初级
- 分类: 背包
问题描述
有一个天平，天平左右两边各有若干个钩子，总共有 C 个钩子，有 G 个钩码，求将钩码全部挂到钩子上使天平平衡的方法的总数。
其中可以把天枰看做一个以 x 轴 0 点作为平衡点的横轴。
输入：
2 4 // C 钩子数 与 G 钩码数
-2 3 // 负数：左边的钩子距离天平中央的距离；正数：右边的钩子距离天平中央的距离 c[k]
3 4 5 8 // G 个重物的质量 w[i]解题思路
提示：动态规划，01 背包
初看此题第一个冲动就是穷举。。。。不过再细想肯定行不通，O(20^20) 等着超时吧。。。
我也是看了前辈的意见才联想到 01 背包，用动态规划来解。
dp 思路：
每向天平中方一个重物，天平的状态就会改变，而这个状态可以由若干前一状态获得。
首先定义一个 平衡度 j 的概念：
- 当平衡度
j=0时，说明天枰达到平衡 j>0说明天枰倾向右边（x 轴右半轴）j<0则相反
那么此时可以把平衡度 j 看做为衡量当前天枰状态的一个值，
因此可以定义一个 状态数组 dp[i][j]，意为在挂满前 i 个钩码时，平衡度为 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 时天枰为平衡状态。
那么每次挂上一个钩码后，对平衡状态的影响因素就是每个钩码的 力臂：力臂 = 重量 *臂长 = w[i] * c[k] 。
若在挂上第 i 个砝码之前，天枰的平衡度为 j (换言之把前 i-1 个钩码全部挂上天枰后，天枰的平衡度为 j )，
则挂上第 i 个钩码后，即把前i个钩码全部挂上天枰后，天枰的平衡度 j = j + w[i] * c[k]，其中 c[k] 为天枰上钩子的位置，代表第 i 个钩码挂在不同位置会产生不同的平衡度
不难想到：
- 假设
dp[i-1][j]的值已知，设dp[i-1][j] = num（即已知把前 i-1 个钩码全部挂上天枰后得到状态 j 的方法有 num 次） - 那么
dp[i][ j+ w[i]*c[k] ] = dp[i-1][j] = num(即以此为前提，在第 k 个钩子挂上第 i 个钩码后，得到状态j + w[i] * c[k]的方法也为 num 次)
想到这里，利用递归思想，不难得出 状态方程 dp[i][ j + w[i] * c[k] ]= ∑(dp[i-1][j])
有些前辈推导方式稍微有点不同，得到的 状态方程为 dp[i][j] = ∑(dp[i-1][j - c[i] * w[i]])
其实两条方程是等价的，这个可以简单验证出来，而且若首先推导到第二条方程，也必须转化为第一条方程，这是为了避免下标出现负数。
结论 - 最终转化为 01 背包问题：
- 状态方程：
dp[i][ j + w[i] * c[k] ]= ∑(dp[i-1][j]) - 初始化：
dp[0][7500] = 1不挂任何重物时天枰平衡，此为一个方法 - 复杂度：
O(C*G*15000)完全可以接受
AC 源码
//Memory Time
//1496K 0MS
//我所使用的解题方法，由于dp状态方程组申请空间比较大大
//若dp为局部数组，则会部分机器执行程序时可能由于内存不足会无法响应
//所以推荐定义dp为全局数组，优先分配内存
#include<iostream>
using namespace std;
int dp[21][15001]; //状态数组dp[i][j]
//放入（挂上）前i个物品（钩码）后，达到j状态的方法数
int main(int i,int j,int k)
{
int n; //挂钩数
int g; //钩码数
int c[21]; //挂钩位置
int w[21]; //钩码重量
/*Input*/
cin>>n>>g;
for(i=1;i<=n;i++)
cin>>c[i];
for(i=1;i<=g;i++)
cin>>w[i];
/*Initial*/
memset(dp,0,sizeof(dp)); //达到每个状态的方法数初始化为0
dp[0][7500]=1; //7500为天枰达到平衡状态时的平衡度
//放入前0个物品后，天枰达到平衡状态7500的方法有1个，就是不挂钩码
/*DP*/
for(i=1;i<=g;i++)
for(j=0;j<=15000;j++)
if(dp[i-1][j]) //优化，当放入i-1个物品时状态j已经出现且被统计过方法数，则直接使用统计结果
//否则忽略当前状态j
for(k=1;k<=n;k++)
dp[i][ j+w[i]*c[k] ] += dp[i-1][j]; //状态方程
/*Output*/
cout<<dp[g][7500]<<endl;
return 0;
}
