注册 登录
编程论坛 数据结构与算法

天平 算法

fengsjack 发布于 2010-06-17 19:00, 1610 次点击
天平
Description
索里嘎有一个天平和n个砝码,天平的两边都能放砝码。他想知道用他的天平和n个砝码能够准确称量的质量有几种。比如,n=2, 砝码的质量分别为1,3。则他能称的质量有1,2,3,4。


Input
第一行有一个正整数n,便是砝码的数量(1<=n<=100)。
接下来是n个正整数,分别表示砝码的质量,(不大于1000)。


Output
输出只有一个正整数,即能够称的质量有几种。


Sample Input
4
1 2 3 8


Sample Output
14
7 回复
#2
audioMan862010-06-20 16:53
这个问题,倒是可以转换为从一个N个数的集合中,取出X和Y个砝码,其中x + y <= N,求x个和Y个砝码的重量和的差的绝对值。所以关键是在取x个砝码
#3
audioMan862010-06-20 16:55
可以利用集合和子集合去取这x个砝码
#4
audioMan862010-06-21 12:07
呵呵,早上没事,在公司写了这个算法,效果还行,不过暂时只能最多支持31个砝码,有时间再改进一下,可是我要怎么才能 把代码贴上来了,公司的网络只能是远程的,所以不能复制,郁闷中
#5
crpchen2010-07-09 17:22
看看
#6
acman2010-08-21 11:32
DP 吧  就是 每一次加的时候 有两种情况了啊 就是 减去他 和家还是那个他  就行了  应该不是很难的啊
1