Re: [請益] 如何把一堆數字分成總合相等的兩個集合
看板Prob_Solve (計算數學 Problem Solving)作者ablboy (賣悶! 賣共! (M))時間17年前 (2007/09/25 16:30)推噓1(1推 0噓 0→)留言1則, 1人參與討論串6/8 (看更多)
有個快速但不確定是不是最佳的解法
先不論正實數的處理
首先將整個陣列由大到小排列
例如 : 20 15 6 5 4 3 2 1
準備兩個空間存放(S1與S2)
依序將數字存放置此兩空間
當某空間目前總和大於另一空間時
下一個數目存入較小的空間中
過程大致如下
20 : sum(S1) = 0, sum(S2) = 0; (S1沒比S2大); S1 <= 20
15 : sum(S1) = 20, sum(S2) = 0; (S1大於S2) ; S2 <= 15
6 : sum(S1) = 20, sum(S2) = 15; (S1大於S2) ; S2 <= 6
5 : sum(S1) = 20, sum(S2) = 21; (S1小於S2) ; S1 <= 5
......
依此類推得到
S1 = 20 5 3
S2 = 15 6 4 2 1
由於沒拿更多數據來測試
我想應該會有特殊情形
等有人提出來特殊數據再來討論！
※ 引述《mmnnmn (12k3jladk)》之銘言：
: ※ 引述《mmnnmn (12k3jladk)》之銘言：
: : 最近我遇到一個問題
: : 假設有n個正數
: : a1,a2,....an
: : 有沒有有效率一點的方法把這n個數分為2個set
: : {s1與s2沒有交集,且s1與s2聯集為這n個數}
: : 使得 sum(s1) == sum(s2)
: : 不完全相等也可以,那麼差要最小
: : 目前我只想到暴搜,複雜度是指數成長><
: : 懇請大家不吝指教..謝謝
: 經過一陣思考,加上實驗室學妹蠻天才的 ☆`' ◆-◆'
: 這是個 NP-complete 的 equal partition problem
: 如果我的data都是integer的話,有機會用DP來解則是pseudo-polynomail time
: 可參考 http://en.wikipedia.org/wiki/Partition_problem
: 不幸的是......我的data是positive real number
: 還有大大能提供我進一步的想法嗎..就算是多一點search path cut rule也好
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.203.0.230
推
09/26 23:38, , 1F
09/26 23:38, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 8 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-4
30