[問題] 一堆數字取組合最大值

看板C_and_CPP作者 (michael)時間10年前 (2013/10/04 16:51), 編輯推噓6(6推 0噓 21→)
留言27則, 12人參與, 最新討論串1/4 (看更多)
開發平台(Platform): (Ex: VC++, GCC, Linux, ...) C 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 無 問題(Question)： 一筆資料長相如下： 資料 第一欄 第二欄 1st： 231 246 2nd： 523 142 3rd： 78 982 4th： 542 333 . . . . . . . . . . . . . . . . . . Nth： 780 98 共有N筆資料，我想要取其中任意K組（此值固定，會在input先得知） 使(第一欄的和)*(第二欄的和)最大，要怎麼取？ 例如說K=3，那答案就是（我自己亂假設的）第一、第三和第N筆 所以答案為：(231+78+780)*(246+982+98) 請問如果要全部找一遍的話，要怎麼找會比較快呢？ 我目前用遞迴，把全部可能的組合都找出來，可是這樣在遇到K=N/2附近的時候 會算很久，我自己估計的複雜度是O(n^K) 請問有沒有更快的找法呢？ 謝謝大家 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 1.34.223.220 ※ 編輯: friendever 來自: 1.34.223.220 (10/04 17:17)
→
10/04 17:45, , 1F
這些數字會有負數嗎?
10/04 17:45, 1F
→
10/04 18:02, , 2F
不會有，也不用考慮會overflow的問題
10/04 18:02, 2F
→
10/04 19:02, , 3F
我在想是不是可以用 sort 配上 divide & conquer 做...
10/04 19:02, 3F
→
10/04 19:02, , 4F
不會有負數就不用考慮負負得正的豬羊變色問題了
10/04 19:02, 4F
推
10/04 19:50, , 5F
把值取自然對數？不太確定…
10/04 19:50, 5F
推
10/05 01:03, , 6F
沒有負數就兩邊都找出前k大的值不就好了
10/05 01:03, 6F
推
10/05 01:06, , 7F
喔我看錯了 組要一起取 請忽略我說的話 抱歉
10/05 01:06, 7F
→
10/05 01:52, , 8F
先累加?
10/05 01:52, 8F
→
10/05 02:29, , 9F
似乎可以去掉一些不可能入選的爛數字, 不過這也只能算
10/05 02:29, 9F
→
10/05 02:30, , 10F
heuristic不算algorithm, 對 worst case 好像也沒幫助
10/05 02:30, 10F
推
10/05 04:21, , 11F
是說直接暴搜所有組合的複雜度是 O(C(n,k))
10/05 04:21, 11F
→
10/05 04:21, , 12F
k 小的話當它 O(n^k) 沒關係 不過如果 k 也會到 n/2 就很糟
10/05 04:21, 12F
→
10/05 04:24, , 13F
由卡塔蘭數的估計 C(n,n/2) 約可估計為 O(2^n/√n)
10/05 04:24, 13F
→
10/05 04:25, , 14F
所以基本上這個做法是指數成長的
10/05 04:25, 14F
→
10/05 17:41, , 15F
我找到方法了,出乎意料地簡單 =.=
10/05 17:41, 15F
→
10/05 17:42, , 16F
可惜推文長度寫不下
10/05 17:42, 16F
→
10/05 17:43, , 17F
先取一個積分最高的,再尋找下一個候選人讓兩數總積分最高
10/05 17:43, 17F
→
10/05 17:44, , 18F
如此一個一個找,複雜度只有O(n^2)
10/05 17:44, 18F
→
10/05 18:02, , 19F
(3,3)(1,6)(6,1)選2組,樓上作法碰到這組會有什麼結果?
10/05 18:02, 19F
→
10/05 18:05, , 20F
k=2時會出槌沒錯,但是n和k都很大的時候,Σx>>x,Σy>>y
10/05 18:05, 20F
→
10/05 18:05, , 21F
此時就不會出現你說的情形了
10/05 18:05, 21F
推
10/05 20:42, , 22F
請問有沒有數字的範圍？
10/05 20:42, 22F
→
10/05 20:43, , 23F
每一筆數字的上界 下界, 或總和的上界之類
10/05 20:43, 23F
推
10/05 20:48, , 24F
這好像是Boolean Quadratic Programming 的一種，很可能是
10/05 20:48, 24F
→
10/05 20:48, , 25F
NP-hard
10/05 20:48, 25F
→
10/05 21:13, , 26F
我直覺也是 NP-hard
10/05 21:13, 26F
→
10/05 23:08, , 27F
分群先處理呢 以數量級作單位 (2.2)(5.1)(0.9)(5.3)...
10/05 23:08, 27F
‣ 更多 friendever 的文章
文章代碼(AID): #1IJe5qsp (C_and_CPP)
‣ 更多 friendever 的文章
文章代碼(AID): #1IJe5qsp (C_and_CPP)