作者ablboy (卖闷! 卖共! (M))
看板Prob_Solve
标题Re: [请益] 如何把一堆数字分成总合相等的两个集合
时间Tue Sep 25 16:29:59 2007
有个快速但不确定是不是最佳的解法
先不论正实数的处理
首先将整个阵列由大到小排列
例如 : 20 15 6 5 4 3 2 1
准备两个空间存放(S1与S2)
依序将数字存放置此两空间
当某空间目前总和大於另一空间时
下一个数目存入较小的空间中
过程大致如下
20 : sum(S1) = 0, sum(S2) = 0; (S1没比S2大); S1 <= 20
15 : sum(S1) = 20, sum(S2) = 0; (S1大於S2) ; S2 <= 15
6 : sum(S1) = 20, sum(S2) = 15; (S1大於S2) ; S2 <= 6
5 : sum(S1) = 20, sum(S2) = 21; (S1小於S2) ; S1 <= 5
......
依此类推得到
S1 = 20 5 3
S2 = 15 6 4 2 1
由於没拿更多数据来测试
我想应该会有特殊情形
等有人提出来特殊数据再来讨论！
※ 引述《mmnnmn (12k3jladk)》之铭言：
: ※ 引述《mmnnmn (12k3jladk)》之铭言：
: : 最近我遇到一个问题
: : 假设有n个正数
: : a1,a2,....an
: : 有没有有效率一点的方法把这n个数分为2个set
: : {s1与s2没有交集,且s1与s2联集为这n个数}
: : 使得 sum(s1) == sum(s2)
: : 不完全相等也可以,那麽差要最小
: : 目前我只想到暴搜,复杂度是指数成长><
: : 恳请大家不吝指教..谢谢
: 经过一阵思考,加上实验室学妹蛮天才的 ☆`' ◆-◆'
: 这是个 NP-complete 的 equal partition problem
: 如果我的data都是integer的话,有机会用DP来解则是pseudo-polynomail time
: 可参考 http://en.wikipedia.org/wiki/Partition_problem
: 不幸的是......我的data是positive real number
: 还有大大能提供我进一步的想法吗..就算是多一点search path cut rule也好
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 203.203.0.230
1F：推 pigalan:Try it: 8 4 3 3 3 3...正确的应该是{8,4}, {3,3,3,3} 09/26 23:38