Re: [討論] GCJ結束了我要伸解法～
看板Prob_Solve (計算數學 Problem Solving)作者Lucemia (生の直感、死の予感)時間16年前 (2008/07/29 20:36)推噓1(1推 0噓 0→)留言1則, 1人參與討論串5/6 (看更多)
※ 引述《yoco315 (眠月)》之銘言：
: ※ 引述《yyc1217 (somo)》之銘言：
: : 不過的確是最大配最小
: 我可以問一下證明嗎
: 雖然到處看到都是這個解答
: 不過我不是很懂為什麼這樣 work
假設 vector1是 (a1,a2,... an),vector2 是 (b1, b2,... bn)
n = 2時很好證:
n = k 時
假設最大配最小解法不為最好,
則存在一組向量為最好
其中至少存在一組 i, j <= n
滿足ai < aj, bi < bj
此組向量內積為
S = a1 * b1 + a2 * b2 + ...ak * bk
= sum(ak | k 不等於 i, j) + ai * bi + aj * bj
> sum(ak | k 不等於 i, j) + ai * bj + aj * bi
(由n = 2時得到結果 )
與假設相抵
故可以歸繆得證
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.88.50
※ 編輯: Lucemia 來自: 140.113.88.50 (07/29 20:39)
推
08/03 03:46, , 1F
08/03 03:46, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 5 之 6 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
