Re: [請益] 如何把一堆數字分成總合相等的兩個集合
看板Prob_Solve (計算數學 Problem Solving)作者scan33scan33 (亨利喵)時間17年前 (2007/09/05 21:58)推噓1(1推 0噓 1→)留言2則, 2人參與討論串2/8 (看更多)
※ 引述《mmnnmn (12k3jladk)》之銘言：
: 最近我遇到一個問題
: 假設有n個正數
: a1,a2,....an
: 有沒有有效率一點的方法把這n個數分為2個set
: {s1與s2沒有交集,且s1與s2聯集為這n個數}
: 使得 sum(s1) == sum(s2)
: 不完全相等也可以,那麼差要最小
: 目前我只想到暴搜,複雜度是指數成長><
: 懇請大家不吝指教..謝謝
如果隨便分的話....
不就,開一個array存現有sum
對每個ai(i belong to 1~n),丟進去sumtable對所有sum加ai
最後再把ai丟入sum table.
sum table的element不要重複,這可以用一段連續記憶體來存!!
n個數字,和最多應該是2^n-1
這樣好像有點多.
所以就加點小cut好了.
就你想要做的是,找到最接近他的平均值的,
因為只要有一個最接近,另一個也會最接近!(這你想想吧!應該Ok)
所以只要找比較小的那個就好喵!
所有超過平均值的都可以不要.
namely,
if sum[i] + aj > mean 就不要丟入 sum table.
這是在下直覺的想法喵>w<.
歡迎指教
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.45
※ 編輯: scan33scan33 來自: 140.112.30.45 (09/05 21:59)
※ 編輯: scan33scan33 來自: 140.112.30.45 (09/05 22:03)
→
09/05 22:04, , 1F
09/05 22:04, 1F
推
09/06 11:28, , 2F
09/06 11:28, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 8 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
