曲棍球池算法

Question

這是一個有趣的項目，我已經開始嘗試並最大限度地獲得贏得我們辦公室曲棍球池的機會。我試圖找到最好的方法來選擇20個球員，這將給我最高工資上限內的最高分。

例如，假設原始數據是由

1. 玩家姓名
2. 位置（前鋒，防守隊員，守門員）
3. 本賽季
4. 支薪點的預測量。

現在我想要20名球員，這將給我X點薪金範圍內的最多點。後來，作爲第二階段，我想做同樣的事情，但在這種情況下，我只需要12位前鋒，6位後衛和2位守門員。

現在顯而易見的方法是簡單地進行各種可能的組合，然而儘管這會起作用，但對於500名玩家來說這不是一個有效的選擇，這將會有太多可能的組合。我可以添加一些智能過濾器，將500名球員減少到前50名前鋒，前30名後衛和前15名門將，但這仍然是一個非常緩慢的過程。

我想知道是否有其他算法來實現這一點。這只是爲了好玩，而不是重要的商業要求。但是，如果您對如何繼續操作有一些想法，請告訴我。

我的第一次嘗試是使用揹包算法和其他來源的幫助。它似乎只用Salary作爲參數。我正在努力研究如何添加20人球員參數。它在.Net中，但應該很容易轉換爲Java。

我正在考慮做一個單獨的循環來找出最好的球隊與20名球員無薪工資，然後比較這兩個名單，直到我找到兩個名單上最高的球隊。不確定。

namespace HockeyPoolCalculator 
{ 
public class ZeroOneKnapsack 
{ 

protected List<Item> itemList = new List<Item>(); 
protected int maxSalary = 0; 
protected int teamSize = 0; 
protected int teamSalary = 0; 
protected int points = 0; 
protected bool calculated = false; 

public ZeroOneKnapsack() { } 

public ZeroOneKnapsack(int _maxSalary) 
{ 
setMaxSalary(_maxSalary); 
} 

public ZeroOneKnapsack(List<Item> _itemList) 
{ 
setItemList(_itemList); 
} 

public ZeroOneKnapsack(List<Item> _itemList, int _maxSalary) 
{ 
setItemList(_itemList); 
setMaxSalary(_maxSalary); 
} 

// calculte the solution of 0-1 knapsack problem with dynamic method: 
public virtual List<Item> calcSolution() 
{ 
int n = itemList.Count; 

setInitialStateForCalculation(); 
if (n > 0 && maxSalary > 0) 
{ 
List<List<int>> playerList = new List<List<int>>(); 
List<int> salaryList = new List<int>(); 

//initialise list 
playerList.Add(salaryList); 
for (int j = 0; j <= maxSalary; j++) 
salaryList.Add(0); 
// Loop through players 
for (int i = 1; i <= n; i++) 
{ 
List<int> prev = salaryList; 
playerList.Add(salaryList = new List<int>()); 
for (int j = 0; j <= maxSalary; j++) 
{ 
if (j > 0) 
{ 
int wH = itemList.ElementAt(i - 1).getSalary(); 
// Is the players salary more than the current calculated salary? If yes, then keep current max points, else get the highest amount between previous max points at that salary and new max points. 
salaryList.Add((wH > j)?prev.ElementAt(j): Math.Max(prev.ElementAt(j),itemList.ElementAt(i - 1).getPoints() + prev.ElementAt(j - wH))); 
} 
else 
{ 
salaryList.Add(0); 
} 
} // for (j...) 
} // for (i...) 
points = salaryList.ElementAt(maxSalary); 

for (int i = n, j = maxSalary; i > 0 && j >= 0; i--) 
{ 
int tempI = playerList.ElementAt(i).ElementAt(j); 
int tempI_1 = playerList.ElementAt(i - 1).ElementAt(j); 
if ((i == 0 && tempI > 0)||(i > 0 && tempI != tempI_1)) 
{ 
Item iH = itemList.ElementAt(i - 1); 
int wH = iH.getSalary(); 
iH.setInKnapsack(1); 
j -= wH; 
teamSalary += wH; 
} 
} // for() 
calculated = true; 
} // if() 
return itemList; 
} 

// add an item to the item list 
public void add(String name, int Salary, int value) 
{ 
if (name.Equals("")) 
name = "" + (itemList.Count() + 1); 
itemList.Add(new Item(name, Salary, value)); 
setInitialStateForCalculation(); 
} 

// add an item to the item list 
public void add(int Salary, int value) 
{ 
add("", Salary, value); // the name will be "itemList.size() + 1"! 
} 

// remove an item from the item list 
public void remove(String name) 
{ 
for (int pointer = 0; pointer <= itemList.Count-1; pointer++) 

{ 
itemList[pointer].getName().Equals(""); 

if (itemList.ElementAt(pointer).getName().Equals(itemList.ElementAt(pointer).getName())) 
{ 
itemList.Remove(itemList.ElementAt(pointer)); 
} 
} 
setInitialStateForCalculation(); 
} 

// remove all items from the item list 
public void removeAllItems() 
{ 
itemList.Clear(); 
setInitialStateForCalculation(); 
} 

public int getPoints() 
{ 
if (!calculated) 
calcSolution(); 
return points; 
} 

public int getSolutionSalary() { return teamSalary; } 
public bool isCalculated() { return calculated; } 
public int getMaxSalary() { return maxSalary; } 

public void setTeamSize(int _teamSize) 
{ 
teamSize = _teamSize; 
} 

public int getTeamSize() 
{ 
return teamSize; 
} 

public void setMaxSalary(int _maxSalary) 
{ 
maxSalary = Math.Max(_maxSalary, 0); 
} 

public void setItemList(List<Item> _itemList) { 
if (_itemList != null) { 
itemList = _itemList; 
foreach (Item item in _itemList) { 
item.checkMembers(); 
} 
} 
} 

// set the member with name "inKnapsack" by all items: 
private void setInKnapsackByAll(int inKnapsack) { 
foreach (Item item in itemList) 
if (inKnapsack > 0) 
item.setInKnapsack(1); 
else 
item.setInKnapsack(0); 
} 

// set the data members of class in the state of starting the calculation: 
protected void setInitialStateForCalculation() 
{ 
setInKnapsackByAll(0); 
calculated = false; 
points = 0; 
teamSalary = 0; 
teamSize = 0; 
} 

} 
} 

感謝您的幫助！

Answer 1

不幸的是，你不應該期望找到一個很好的解決方案，因爲它是NP-hard。除非P = NP，沒有任何多項式時間算法，窮舉搜索可能是最好的算法之一（儘管您可能使用一些啓發式算法來加速它）。

爲了看到這個問題是NP難題，我們將展示如何在多項式時間內減少knapsack problem。給定由一組S = {（重量，值）的子集和問題的任何實例，（重量，值），...，（重量_Ñ，值 _n）}和權重極限k，我們可以通過創建一組球員來製作一個曲棍球問題的實例，這些球員的薪水是體重，其預期分數就是價值。然後我們嘗試找到薪水不超過k的球員的最大重量組合，然後與原始揹包問題中不超過目標體重的最大總和相同。

由於您發佈的代碼顯示，但有一個pseudopolynomial時間算法來解決揹包問題。假設工資很低（或者你可以將它們歸一化爲小數目），你可能可以使用這個效果。

雖然有一個多項式時間算法來得到確切的答案是值得懷疑的，但如果對於一個近似最優的解決方案沒問題的話，還有一個多項式時間算法來近似解決揹包問題。有關詳細信息，請查看these notes，其中詳細介紹了兩種算法。有趣的是，它們依賴於你似乎正在使用的假多項式時間算法，所以它們可能很容易實現？

對不起衝你的希望與數學一個很好的解決方案...... NP難的問題往往這樣做。 :-(

Answer 2

劇情上的曲線圖播放器，X軸是分，Y軸是薪水，零在原點。右下玩家將是合乎需要廉價高分，左上玩家將是不合乎需要的昂貴的低分記錄器，對角線上的玩家將是相同的（每點相同的成本）。從X水平逆時針掃描起始錨定半徑到Y垂直，形成不斷增長的扇形片，直到如果你達到$ cap但不是20個玩家，刪除片中的「最左上角」的玩家並繼續，如果你達到了20個玩家，但是沒有達到上限，你可以從切片中刪除一個低分球員，爲更高分的球員騰出空間玩家即將進入切片，使得每點的總成本不必要地上升，但由於這是有趣的錢，而且你不是真正的擁有者，所以就去做吧。

Answer 3

問題可能很難，但你可以使用一個事實，即你的守門員是不是在進攻會打（更正式的：你選擇的實體是不同類型的），以提高你的運行。

此外，您可能希望找到一個近似的解決您的問題。使用該值來限制最佳解決方案並搜索它。

Answer 4

你可以很容易地制定爲ILP。解決它們也是NP-Hard，但問題實例似乎不那麼大，所以它可能是完美的解決方案（一個解算器就是例如lpsolve）。即使由於問題的大小而不能解決問題，對於ILP也存在很好的啓發式。

Answer 5

一個有趣的方式來處理那樣的問題是使用genetic algorithm。而實際上，我只是爲了我自己的曲棍球場而做到了這一點！

你可以看到the whole Scala code here，如果你是好奇，但它的心臟是：

def GA(nbIter: Int, popSize: Int, tournamentSize: Int) = { 
    def loop(iter: Int, pop: Seq[LineUp]): LineUp = { 
    val best = pop.maxBy(_.fitness) 
    println("\nBest of generation " + iter + best) 
    if (iter == nbIter) 
     best 
    else { 
     val newPop = for { 
     _ ← Stream.continually() 
     x = tournament(pop, tournamentSize).head 
     y = (x.mutants take 5) maxBy (_.fitness) 
     } yield y 
     loop(iter + 1, best +: newPop.take(popSize - 1)) 
    } 
    } 
    val initialPop = LineUp.randomStream.take(popSize) 
    loop(0, initialPop) 
} 

它首先產生有效的陣容（尊重的工資帽和位置的限制）的隨機集合。對於每次迭代，然後通過使用tournament selection和hill climbing的組合來生成新的羣體。 「健身」簡單地定義爲最低薪水作爲平局決勝的陣容的預期得分數。

這當然只是一種啓發式的方式，但如果您的玩家名單不算太大，而且您可以負擔得起讓算法運行一段時間，那麼您很可能會找到一個相當優化的解決方案。