尋找最低平均成績差

Question

給定一個有n個男孩和n個女孩的班級，其中女孩獲得了p1，...，pn等級，並且男孩在考試中獲得了s1，...，sn等級，以最小化夫妻成績平均差異的方式找到一對女孩。 例如，如果p1 = 30，p2 = 60，s1 = 50，s2 = 90，我們應該將女孩＃1與男孩＃1（20點差異）和女孩＃2與男孩＃2（30點差異）並且我們將得到（30 + 20）/ 2 = 25的最小平均差值。

證明以下算法是最優的： 將最低年級的女孩與最低年級的男孩配對。配對，然後女孩與第二最低等級對男孩與第二最低等級等

---

以我的解決方案，我嘗試使用貪心選擇屬性（表示存在一個最佳的解決方案，其中某些元件在溶液中，然後用歸納法證明，所有的元素都在最佳的解決方案）：

令A1 < = ... < =一個被女孩的成績排序，B1 < = ... < = Bn是排序的男生成績。

聲明 - 存在一個最佳解決方案，其中包括A1-B1（最低年級女生與成績最低的女生配對）。

證明 - 假設相反，該陳述是錯誤的。因此，沒有最佳解決方案包括A1-B1作爲一對。假設在解中A1-Bi（i> 1）和B1-Aj（j> 1）是成對的。我們知道A1 < = Aj和B1 < = Bi。我如何從這裏繼續？

在此先感謝。

Answer 1

好的，我發現了一些基於幾何觀測的東西。
假設您現在只有4個數字：a1 < = a2和b1 < = b2（0）。

| a1-b1 | + | a2-b2 | < = | a1-b2 | + | a2-b1 | （1）

在這種情況下，我們想檢查（1）是否爲真。

我重寫（1）的基礎上顯而易見的等價關係：

（| A1-B1 | + | A2-B2 |）^ 2 < =（| A1-B2 | + | A2-B1 |）^ 2（2）

-2 * A1 * B1 -2 * A2 * B2 < = -2 * A1 * B2 -2 * A2 * B1（3）

我應該解釋如何從得到（2- ）到（3）？我猜不會。

然後我們得到：

A1 * B1 + A2 * B2> = A1 * B2 + A2 * B1（4）

A1（B1-B2）> = A2 *（B1-B2） （5）

A1（B1-B2） - A2 *（B1-B2）> = 0（6）

A1（B1-B2）+ A2 *（B2-B1）> = 0（7 ）

但是（5）顯然是真的，因爲b1-b2 < = 0和a1 < = a2（參見（0））。

這對於N = 2嚴格證明。

我的直覺告訴我，這應該得到某種
很容易推廣爲N的情況下，也許我們可以試着從這裏的
感應（在看到這些（1），（2），（3）等等。）。

幾何學，可以想像，在艾和Bj爲點
兩個平行的數字LINEX（軸A，軸B）。一個
配對配置由與段連接從A配對
點和B中定義。您的聲明基本上是
表示最佳配對是其中沒有兩個段（Ai，Bj）彼此交叉（它們可以與
彼此重疊/在最優解決方案中/但可能彼此不交叉） 。
對不對？現在

，如果我們做同樣的事情（這我做了N = 2），
任何N，你會得到這樣一個問題：「是
A1（B1-BI 1）+ A2（B2- BI2）+ A3（B3-BI3）+ ... + AN *（BN-BIN）> = 0（4' ）
真」，其中I1，I2，...，IN的任何置換（1， 2，...，N），
並且考慮到A [1] = < A [1 + 1]和b [i]於< = b [I + 1]對於每個i。

現在，我們在這裏做N個感應證明（4' ）。
假設（4'）對於N和對於所有K都成立，使得K < N.
對A和B增加兩個數字。假設aN + 1和bN + 1。
假設它們以其各自的SORTED序列（A，B）插入位置s1（在A中）和s2（在B中）
中。假設s1 < = s2
（相反的情況是類比的）。所以現在as1 = aN + 1和bs2 = bN + 1，
但是s1和s2是它們在NEW排序序列中的實際指數。

但是，現在證明（4「）爲N + 1變成的
證明它對於N = 2的問題，因爲只有這些術語（從（4」））
無論我們何時做從N到步驟N + 1。

AS1 *（BS1 - BS2）+ AS2 *（BS2 - BS1）> = 0（7' ）
和正如我們看到的，這是對於N = 2真（見上述（7））。

對於其它N-1項（其保持從（4「））中，我們得到了
不等式（4」）爲真，由於從感應的假設（它是
真用於N-1）。因此，根據2和N-1的真值，我們得到了N + 1的真值。
希望你明白我是怎麼做到的。在紙上，它更容易
寫它，很難寫在這裏。

所以這應該是你對N情況的嚴格證明。

Answer 2

好的。假設我們有：

P1 < = P2 < = ... < =光合速率， 和 S1 < = S2 < = ... < =錫。

我們假設這個陳述不是真的， 還有另一個最佳解決方案。 這意味着我們假設P1與Sk配對，其中k> 1。

現在讓我們來看看這其中與S1配對點Pj（如果你畫
它作爲一個圖，這兩條線P1-SK和PJ-S1將相互交叉）。

所以我對前兩行彼此交叉感興趣。

現在想想如果我們採用相同的配置會發生什麼，但我們通過將P1與S1以及Pj與Sk配對來更改 。總和將減少 （或者如果P1 = Pj或S1 = Sk，它可以保持不變）。

實施例：

但是，如果它保持不變，我們可以在兩個序列向前前進。

事實證明，我們的最佳解決方案並不是最優的。 這是矛盾的，所以我們的假設是不正確的。注1：實際上，在我的證明中，我應該說的不是P1， ，而是具有最小m的Pm，因此Pm不與Sm 配對，但有一些Sk，其中k> m。 我在這裏說過P1只是爲了簡單。

注2：爲了證明這一部分：
。「現在想想，如果採取同樣的配置，但 相反，我們與S1和點Pj對P1與SK的總和將減少發生的事情」 只是覺得，如果你有4個數字會發生什麼只有
P1 < = P2
S1 < = S2

那麼你應該將它們配對：P1-S1和P2-S2或交叉對像
P1- S2和S1-P2。這裏需要解決幾個不同的情況。

11（夫婦1 - 數量相等）
2 2（夫婦2 - 也相等數量）

1 3（不同的號碼）
2 2（相等數量）

1 5（不同的號碼）
2 10（不同的號碼）

注3：OK，我覺得有些邊界情況和細節應該
制定出:)但基本上這個想法應該工作。

Answer 3

Observe that: 
- no matter how you arrange the pairs, the sums of each set will be constant, and so will be the difference between the two sums. 
- the 'sum of differences' can only be equal or greater than the 'difference of sums' 

那麼，什麼是讓比「總和的差異」更大「的差異之」？

This is how I would structure the proof: 
1) what you want to prove is that sorting minimizes the cases that make the 'sum of differences' greater. 
2) what can make the 'sum of differences' greater than the 'difference of sums' are the pairs where the size relation is opposite to the size relation of the sums. For example, if in your sample the sum of all the P grades is greater than the sum of all the S grades (sumP > sumS), any pair where p < s. 
3) Now, all you have to prove is that any non-sorted arrangement can only make things worse. 

(Forgive the absence of proper math language and depth, I have an excuse for the first though, I'm new to SO and still trying to master the editor) 

Answer 4

您正在嘗試尋找最小的平均差異。那麼什麼是平均差：1/n *（（p1-s1）+（p2-s2）+ ... +（pn-sn））它是1/n *（（p1 + p2 + .. + pn） - （s1 + s2 + .. + sn）），這似乎不依賴於排序。那麼你可以對它進行分類和配對，它將具有最小的平均距離以及任何其他順序。