回 帖 发 新 帖 刷新版面

主题:数字串平分

给你一串无序数字....比如说是1 2 3  4 5 6 7 8 9 10 11 
让你找出两串数字..使他们的和相同...


我的想法是先对数字串进行排序.然后求出他们的sum ,再sum=sum/2;  如果不能被2整除.就一定不能平分。.不然..就将sum减去最大的数,并将剩余的值赋给sum,然后从再从比sum小的数里减去那个段里最大的数....如此循环。.如果减去某个数字刚好为0,就找到了。,如果不能为0.就回去..从把次大的那个再减去。..但是实现起来好象很困难。...\
不知道有没有别的什么思路。..谢谢各位了

回复列表 (共2个回复)

沙发

天啊,这是dp题……………………
用dp[n,m]表示前n个数中通过加减运算能得到m的方法种数,则:
dp[n,m]=dp[n-1,m+num[i]]+dp[n-1,m-num[i]]
如果要得到确切的方案就麻烦点了,要在每一个状态里记录每一个方案,在转移的过程中再维护这个方案……

板凳

不用dp也可以

我来回复

您尚未登录,请登录后再回复。点此登录或注册