作者scan33scan33 (亨利喵)
看板Prob_Solve
标题Re: [请益] 如何把一堆数字分成总合相等的两个集合
时间Wed Sep 5 21:58:50 2007
※ 引述《mmnnmn (12k3jladk)》之铭言：
: 最近我遇到一个问题
: 假设有n个正数
: a1,a2,....an
: 有没有有效率一点的方法把这n个数分为2个set
: {s1与s2没有交集,且s1与s2联集为这n个数}
: 使得 sum(s1) == sum(s2)
: 不完全相等也可以,那麽差要最小
: 目前我只想到暴搜,复杂度是指数成长><
: 恳请大家不吝指教..谢谢
如果随便分的话....
不就,开一个array存现有sum
对每个ai(i belong to 1~n),丢进去sumtable对所有sum加ai
最後再把ai丢入sum table.
sum table的element不要重复,这可以用一段连续记忆体来存!!
n个数字,和最多应该是2^n-1
这样好像有点多.
所以就加点小cut好了.
就你想要做的是,找到最接近他的平均值的,
因为只要有一个最接近,另一个也会最接近!(这你想想吧!应该Ok)
所以只要找比较小的那个就好喵!
所有超过平均值的都可以不要.
namely,
if sum[i] + aj > mean 就不要丢入 sum table.
这是在下直觉的想法喵>w<.
欢迎指教
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.45
※ 编辑: scan33scan33 来自: 140.112.30.45 (09/05 21:59)
※ 编辑: scan33scan33 来自: 140.112.30.45 (09/05 22:03)
1F：→ scan33scan33:有要|s1|-|s2|=1的话作法会不一样唷喵!>w< 09/05 22:04
2F：推 mmnnmn:感谢scan33scan33大,正整数的确有差 m(_ _)m 09/06 11:28