作者ablboy (卖闷! 卖共! (M))
站内Prob_Solve
标题Re: [请益] 如何把一堆数字分成总合相等的两个集合
时间Thu Sep 27 09:16:13 2007
依网友的数据再推一次
首先将整个阵列由大到小排列
例如 : 8 4 3 3 3 3
准备两个空间存放(S1与S2)
依序将数字存放置此两空间
当某空间目前总和大於另一空间时
下一个数目存入较小的空间中
过程大致如下
8 : sum(S1) = 0, sum(S2) = 0; (S1没比S2大); S1 <= 8
4 : sum(S1) = 8, sum(S2) = 0; (S1大於S2) ; S2 <= 4
3 : sum(S1) = 8, sum(S2) = 4; (S1大於S2) ; S2 <= 3
3 : sum(S1) = 8, sum(S2) = 7; (S1小於S2) ; S2 <= 3
......
依此类推得到
S1 = 8 3
S2 = 4 3 3 3
到此时S1与S2相差1
因此找S2的元素集合(排列组合)与S1元素中差值为 1的做交换
例如: S2的4 与 S1的3
例如: S2的3 3 3 与 S1的8
不过我想应该还有特殊数据
等网友提出来在讨论
:
-- 恕删 --
: --
:
※ 发信站: 批踢踢实业坊(ptt.cc)
: ◆ From: 203.203.0.230
: 推 pigalan:Try it: 8 4 3 3 3 3...正确的应该是{8,4}, {3,3,3,3} 09/26 23:38
※ 编辑: ablboy 来自: 203.203.0.230 (09/27 09:18)