Re: [問題] 一堆數字取組合最大值
你好 我有一點想法 不知是否可行:
首先我先描述一下我接下來用的符號
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
→
10/05 21:12, , 1F
10/05 21:12, 1F
你說的沒錯... 後面沒有考慮到交點的問題
→
10/05 23:06, , 2F
10/05 23:06, 2F
對诶哈哈 其實我倆的思考方向應該是雷同的
→
10/05 23:55, , 3F
10/05 23:55, 3F
→
10/05 23:58, , 4F
10/05 23:58, 4F
對喔XD
沒有考慮到交點的部分
這樣看來還是沒辦法避開Cn取k的動作
推
10/05 23:59, , 5F
10/05 23:59, 5F
推
10/06 00:03, , 6F
10/06 00:03, 6F
是的
這樣看起來不能重畫(先剃除一部分再剃除一部分)
因為交點必須要考慮進去
我目前沒有甚麼想法XD
※ 編輯: elfkiller 來自: 114.44.75.123 (10/06 00:58)
※ 編輯: elfkiller 來自: 114.44.75.123 (10/06 00:59)
→
10/06 01:50, , 7F
10/06 01:50, 7F
討論串 (同標題文章)
完整討論串 (本文為第 3 之 4 篇)：
6
27
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
