[請益] 如何把一堆數字分成總合相等的兩個集合

[mmnnmn (12k3jladk)]

最近我遇到一個問題
假設有n個正數
a1,a2,....an
有沒有有效率一點的方法把這n個數分為2個set
{s1與s2沒有交集,且s1與s2聯集為這n個數}
使得 sum(s1) == sum(s2)
不完全相等也可以,那麼差要最小

目前我只想到暴搜,複雜度是指數成長><
懇請大家不吝指教..謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.113.169.32
推 ckclark:聽你的描述和acm10032很像
→ ckclark:不過他還有限制要最多|s1|-|s2|<=1
推 ledia:Difference Subsets Sum 應該也是 NP-complete 吧?
推 seanwu:是正數還是正整數...?
→ mmnnmn:是正數還是正整數有差嗎...?
推 scan33scan33:就是看能不能直接建表吧!>w<
→ scan33scan33:建已存在的值的表?
推 yoco315:np
→ neverfly:這個問題被證明是NP-Hard很久了
推 DJWS:雖然是NP問題  還是可以討論看看有什麼加速的方法呀～
→ DJWS:如果是正整數的話　可以用memoization試試看？