Re: [請益] 如何把一堆數字分成總合相等的兩個集合
看板Prob_Solve (計算數學 Problem Solving)作者mmnnmn (12k3jladk)時間17年前 (2007/09/06 17:16)推噓0(0推 0噓 0→)留言0則, 0人參與討論串3/8 (看更多)
※ 引述《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: 140.113.169.32
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
