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

看板Prob_Solve作者 (12k3jladk)時間16年前 (2007/09/05 19:55), 編輯推噓6(6推 0噓 5→)
留言11則, 8人參與, 最新討論串1/8 (看更多)
最近我遇到一個問題 假設有n個正數 a1,a2,....an 有沒有有效率一點的方法把這n個數分為2個set {s1與s2沒有交集,且s1與s2聯集為這n個數} 使得 sum(s1) == sum(s2) 不完全相等也可以,那麼差要最小 目前我只想到暴搜,複雜度是指數成長>< 懇請大家不吝指教..謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.169.32
推
09/05 20:26, , 1F
聽你的描述和acm10032很像
09/05 20:26, 1F
→
09/05 20:27, , 2F
不過他還有限制要最多|s1|-|s2|<=1
09/05 20:27, 2F
推
09/05 21:19, , 3F
Difference Subsets Sum 應該也是 NP-complete 吧?
09/05 21:19, 3F
推
09/05 23:17, , 4F
是正數還是正整數...?
09/05 23:17, 4F
→
09/06 01:10, , 5F
是正數還是正整數有差嗎...?
09/06 01:10, 5F
推
09/06 01:41, , 6F
就是看能不能直接建表吧!>w<
09/06 01:41, 6F
→
09/06 01:42, , 7F
建已存在的值的表?
09/06 01:42, 7F
推
09/06 08:32, , 8F
np
09/06 08:32, 8F
→
09/06 10:41, , 9F
這個問題被證明是NP-Hard很久了
09/06 10:41, 9F
推
09/06 12:08, , 10F
雖然是NP問題 還是可以討論看看有什麼加速的方法呀～
09/06 12:08, 10F
→
09/06 12:09, , 11F
如果是正整數的話　可以用memoization試試看？
09/06 12:09, 11F
‣ 更多 mmnnmn 的文章
文章代碼(AID): #16tfagew (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 8 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共8篇)
‣ 更多 mmnnmn 的文章
文章代碼(AID): #16tfagew (Prob_Solve)