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

[elfkiller (沒有暱稱)]

你好 我有一點想法 不知是否可行:

首先我先描述一下我接下來用的符號
n組點為(X1, Y1) (X2, Y2)...
題目是從中取出k組使得(Xk1 + Xk2 + ...)*(Yk1 + Yk2 + ...)的和為最大

因為乘號太討厭了, 先把它展開可能好處理一點
展開後樣子會像是是Xk1Yk1 + Xk1Yk2 + ... + Xk2Yk1 + Xk2Yk2 + ...
考慮一下n組點可能形成的組合
可以把它寫成矩陣的樣子(計算複雜度O(n^2))

X1Y1 X2Y1 .... XnY1
X1Y2 X2Y2
 .        .
 .          .
 .            .
X1Yn           XnYn

好的
再來讓我們換個角度考慮一下題目
如果我們不選某一組點這個矩陣會怎麼樣呢?
例如我們不選第二組好了
那麼展開項中就不會有X2跟Y2的項對吧
所以矩陣看起來就會像是

X1Y1  | X3Y1 .... XnY1
______|_______________
      |
X1Y3  | X3Y3
 .    |      .
 .    |        .
 .    |          .
X1Yn  |           XnYn

換句話說, 以對角線上的X2Y2為中心的行列被刪除了
如果我們劃掉n-k組這樣的線
那麼剩下的子矩陣的元素和
不正好就是題目中取出k組後展開式的和嗎?

令S1 = 以X1Y1為中心的行列的和
  S2 = 以X2Y2為中心的行列的和, 依此類推(計算複雜度O(n^2))

到這邊為止
整個題目就轉化成: 從S1 ~ Sn中, 剔除n-k個最小值(可以用排序做, 計算複雜度(nlogn))

以上是一點想法
沒有驗證過
不知道有沒有矛盾之處?
給你參考一下XD

===

附帶一提, 矩陣有夠難畫QQ

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.44.75.123
→ Feis:前面應該是對的. 不過刪除 n-k 的最小值的步驟應該有問題.
你說的沒錯... 後面沒有考慮到交點的問題
→ Schottky:我們是同一掛的 *握手*
對诶哈哈 其實我倆的思考方向應該是雷同的
→ rebaudiana:n-k>1時會有多個交點被重複剃除…
→ rebaudiana:所以不能單純剃除最小的？
對喔XD
沒有考慮到交點的部分
這樣看來還是沒辦法避開Cn取k的動作
推 goliathplus:重畫矩陣就好
推 goliathplus:喔 不能重畫 要同時剃除... 這樣不能直接掛排序 XD
是的
這樣看起來不能重畫(先剃除一部分再剃除一部分)
因為交點必須要考慮進去
我目前沒有甚麼想法XD
※ 編輯: elfkiller       來自: 114.44.75.123        (10/06 00:58)
※ 編輯: elfkiller       來自: 114.44.75.123        (10/06 00:59)
→ Schottky:雖然沒辦法直接排序,但總覺得還是有個模糊的高低標準