討論串(共8篇) - [請益] 如何把一堆數字分成總合相等的兩個集合 - 看板Prob_Solve

看板 [ Prob_Solve ]

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

共 8 篇文章

排序：最舊先 | 最新先 | 留言數 | 推文總分

內容預覽：開啟 | 關閉 | 只限未讀

首頁

尾頁

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

推噓6(6推 )留言11則，0人參與作者mmnnmn (12k3jladk)時間16年前 (2007/09/05 19:55)資訊

內容預覽:

最近我遇到一個問題. 假設有n個正數. a1,a2,....an. 有沒有有效率一點的方法把這n個數分為2個set. {s1與s2沒有交集,且s1與s2聯集為這n個數}. 使得 sum(s1) == sum(s2). 不完全相等也可以,那麼差要最小. 目前我只想到暴搜,複雜度是指數成長><. 懇請大

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

推噓1(1推 )留言2則，0人參與作者scan33scan33 (亨利喵)時間16年前 (2007/09/05 21:58)資訊

內容預覽:

如果隨便分的話..... 不就,開一個array存現有sum. 對每個ai(i belong to 1~n),丟進去sumtable對所有sum加ai. 最後再把ai丟入sum table.. sum table的element不要重複,這可以用一段連續記憶體來存!!. n個數字,和最多應該是2^n

(還有207個字)

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

推噓0(0推 )留言0則，0人參與作者mmnnmn (12k3jladk)時間16年前 (2007/09/06 17:16)資訊

內容預覽:

經過一陣思考,加上實驗室學妹蠻天才的 ☆`' ◆-◆'. 這是個 NP-complete 的 equal partition problem. 如果我的data都是integer的話,有機會用DP來解則是pseudo-polynomail time. 可參考 http://en.wikipedia.

(還有14個字)

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

推噓0(0推 )留言0則，0人參與作者yoco315 (眠月)時間16年前 (2007/09/06 18:13)資訊

內容預覽:

目前想到的是. 如果沒要求要 exactly 解的話. 用 GA 倒是可以快速的找出近似解... --. To iterate is human, to recurse is divine.. 遞迴只應天上有, 凡人該當用迴圈. L. Peter Deutsch. --. ※ 發信站: 批踢踢實業坊

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

推噓0(0推 )留言0則，0人參與作者xcycl (XOO)時間16年前 (2007/09/06 21:38)資訊

內容預覽:

把指數部份的調成一樣, 就可以直接拿 mantissa 來比了?. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 220.134.69.245.

首頁

尾頁