如何最大限度地減少4個不同學科的分數總和

在游泳比賽中，有4種不同的筆畫。每位參賽者都參與其中，並記錄完成時間。從所有參賽選手中選出四名選手，這樣他們的組合時間最短（一名選手只能選一名）。不止一個這樣的團隊是可能的，並且所有這樣的團隊都必須打印輸出。如何最大限度地減少4個不同學科的分數總和

例如，假設有四個選手A，B，C和D.它們完成的時間是

A 50.5 52.9 51.8 52.7 
B 50.7 52.7 51.4 52.7 
C 50.7 52.7 51.4 52.8 
D 50.8 52.9 51.6 52.6

這裏，最小時間將是（A - 50.5，C - 52.7，B - 51.4 ，D - 52.6）和（A - 50.5，B - 52.7，C - 51.4，D - 52.6）。

我沒有任何測試用例。我可以用蠻力來做，但這需要O（n^4）。什麼是更好的方法？

2016-11-11 d1729

「以下」對於標題來說確實是一個不好的選擇。 – trincot

如果我正確理解問題，請將數據從行轉換爲列，然後在列之間選擇最小值。這將需要O（n日誌n） – AndyG

聽起來像一個家庭作業問題....你有什麼嘗試，或者你有幾個不同的想法，你已經嘗試過？ – random

無論我們想如何分配其他三個筆畫，在一次筆畫中獲得第五或更糟的最佳時間都是毫無意義的：前四筆之一是可用的。在每個筆畫中選出前四名候選人，然後過濾4*4*4*4 = 256的可能性以確保作業是唯一的。

O（n）（假設比賽的數量是恆定的）。

由於您需要所有的解決方案，因此無法獲得O（n）時間解決方案，因爲其中可能存在指數級的許多解決方案。但是，您可以使用上述算法高效地枚舉它們。在你的蠻力算法中，插入一個使用上述邏輯的測試來確定是否考慮部分分配可以擴展到最佳解決方案。運行時間爲O（n + s），其中s是最優解的數量。

2016-11-11 15:09:51

如果n個候選人在所有比賽中都有相同的時間，那麼不會有n！團隊？如何計算O（n）或O（nlogn）？ – d1729

@ d1729然後你使用上面的邏輯修剪蠻力。 –

回答