[其他] 不知該歸為何類的證明題
今有兩數列 S0、S1，兩數列中皆有N個正整數。
將兩數列之元素兩兩相加後可得新的數列S2，意即
S0 = { S00, S01, ..., S0i, ... , S0N }
S1 = { S10, S11, ..., S1j, ... , S1N }
S2 = { S0i + S1j } ij不重複 >>> S01加過就捨棄，不會再拿出來加一次。
試求一相加的方法，可使S2之變異數為所有相加的組合中最小。
網路搜尋到的方法不外乎兩種。
1. 將S0 sort為 increasing 數列
將S1 sort為 decreasing 數列
S2 = { S00 + S10, S01 + S11, ...., S0N + S1N }
2. 將S0 S1之所有數相加計算平均
尋找 S0 S1 中，相加後與平均最為相近的兩組元素，放入S2中並去除
一直到S0 S1的元素都找完為止
但這兩種方法的正確性，卻不知如何證明。求教 <(_ _)>
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.121.198.160
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1444286212.A.9E7.html
→
10/08 14:44, , 1F
10/08 14:44, 1F
多謝指教! 已成功證明!
第二個方法需用電腦科學中的貪婪演算法證明，那題倒是無礙。
※ 編輯: lovesnake (140.121.198.160), 10/08/2015 15:43:10
→
10/08 16:06, , 2F
10/08 16:06, 2F