[問題] 挑數字問題
看板Prob_Solve (計算數學 Problem Solving)作者flere (人間失格)時間12年前 (2013/01/06 14:13)推噓4(4推 0噓 1→)留言5則, 3人參與討論串1/1
想問一下
給定N個數字 ( 10<=N<=10^6, 數字範圍0~10^8)
假定數字皆不重複
現在要從這N個數字裡面,挑出10個數字
再把這10個數字分成兩堆 (一堆5個
使的兩堆的數字相差要最小
請問這是NP-complete問題嗎?? (不太會分QQ
有什麼快速的做法嗎??
謝謝: )
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.195.203.24
推
01/06 15:59, , 1F
01/06 15:59, 1F
推
01/06 16:38, , 2F
01/06 16:38, 2F
窮舉我想應該是(N取10的組合數) * (分兩堆的時間)
所以這應該是P問題
但是時間複雜度非常的大
這樣理解是對的吧??
※ 編輯: flere 來自: 123.195.203.24 (01/06 17:10)
推
01/07 03:05, , 3F
01/07 03:05, 3F
→
01/07 03:07, , 4F
01/07 03:07, 4F
推
01/07 03:11, , 5F
01/07 03:11, 5F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
