作者mmnnmn (12k3jladk)
站内Prob_Solve
标题Re: [请益] 如何把一堆数字分成总合相等的两个集合
时间Thu Sep 6 17:16:19 2007
※ 引述《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: 140.113.169.32