POJ 1837 Balance解题报告（动态规划）
by NENU_ACM_Club on Aug.05, 2008, under ACM Reports, Hits 907
http://acm.pku.edu.cn/JudgeOnline/problem?id=1837
解法类型：动态规划
题目大意：
输入一个天平若干（<=20）挂钩的位置，将若干（<=20）砝码挂到天平上，问有多少种使天平挂平衡的方法。
解题思路：
用一个二维数组t[x][y+4000]记录挂x个砝码时到y这个值的方法数，将砝码一一挂上，最后记录所有砝码都挂上时的t[x][4000]的值，详见代码。
提交情况：
Wrong Answer若干：开始的时候没想到用二维数组，试图通过两个一维数组不断互相更新，由于操作繁琐，过需花费时间，导致不能遍历每个位置，为了省时，又引 入 记录 值不为0 的t数组相应位置 的数组。导致操作更加繁琐，代码过长，思路虽没什么问题，但零星的错误实在难以找到，最终只好更换思路。
注意：
动态规划类题目状态标记方法 以及标记数组各元素之间的关系 比较多样灵活， 难以想到，这是重点也是难点。
代码:
源程序：
#include <iostream>
using namespace std;
int w[21],h[21],t[21][8000];
/*w数组用来记录砝码的重量，
h数组用来记录天平挂钩的位置，
t的第一位维用来记录已挂上的挂钩的数目
第二维用来记录通过挂砝码
可以到达相应值的方法数*/
int main()
{
int c,g,i,j,k;
while(cin>>c>>g)
{
for(i=1;i<=c;i++) cin>>h[i]; //输入挂钩位置和砝码的重量
for(i=1;i<=g;i++) cin>>w[i];
memset(t,0,sizeof(t)); //初始化可达数数组
for(i=1;i<=c;i++) t[1][w[1]*h[i]+4000]++;
/*挂第一个砝码时对可达数 数组
进行相应的修改 其中+4000
(可知若想使得天平平衡一面最多挂到的值为4000)
是为了将所有值都转到正数组中 方便处理
开始的时候没想到 用了两个数组
这也给编码和调试带来了极大的不便*/
for(i=2;i<=g;i++) //将剩余的砝码一一挂上
for(j=1;j<=c;j++) //循环所有挂钩的位置
for(k=1;k<=8000;k++)
if(t[i-1][k]) t[i][k+w[i]*h[j]]+=t[i-1][k];
/*循环所有值 找到 挂 上一个 砝码后可以达到的值，
然后挂当前砝码，得到 挂当前砝码后
计算得到的对应值 的可达数*/
cout<<t[g][4000]<<endl;
//输出所有砝码都挂上 平衡位置所对应的可达数即为 平衡的方法数
}
return 0;
}
另可见，我(Charlie)在上边有些论述：
http://www.5ushare.com/bbs/viewthread.php?tid=56&extra=page%3D1
http://www.5ushare.com/bbs/viewthread.php?tid=29&extra=page%3D1
Leave a Reply
-
Welcome to 5ushare!
Thanks for dropping by! Feel free to join the discussion by leaving comments, and stay updated by subscribing to the RSS feed. See ya around!
Anything,contact me.Here is My Chinese Blog
