作者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