作者mmnnmn (12k3jladk)
站内Prob_Solve
标题[请益] 如何把一堆数字分成总合相等的两个集合
时间Wed Sep 5 19:55:21 2007
最近我遇到一个问题
假设有n个正数
a1,a2,....an
有没有有效率一点的方法把这n个数分为2个set
{s1与s2没有交集,且s1与s2联集为这n个数}
使得 sum(s1) == sum(s2)
不完全相等也可以,那麽差要最小
目前我只想到暴搜,复杂度是指数成长><
恳请大家不吝指教..谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.169.32
1F：推 ckclark:听你的描述和acm10032很像 09/05 20:26
2F：→ ckclark:不过他还有限制要最多|s1|-|s2|<=1 09/05 20:27
3F：推 ledia:Difference Subsets Sum 应该也是 NP-complete 吧? 09/05 21:19
4F：推 seanwu:是正数还是正整数...? 09/05 23:17
5F：→ mmnnmn:是正数还是正整数有差吗...? 09/06 01:10
6F：推 scan33scan33:就是看能不能直接建表吧!>w< 09/06 01:41
7F：→ scan33scan33:建已存在的值的表? 09/06 01:42
8F：推 yoco315:np 09/06 08:32
9F：→ neverfly:这个问题被证明是NP-Hard很久了 09/06 10:41
10F：推 DJWS:虽然是NP问题 还是可以讨论看看有什麽加速的方法呀～ 09/06 12:08
11F：→ DJWS:如果是正整数的话 可以用memoization试试看？ 09/06 12:09