Алгоритм хоккейного пула

Это небольшой забавный проект, который я начал, чтобы максимально увеличить свои шансы на победу в нашем офисном хоккейном пуле. Я пытаюсь найти лучший способ выбрать 20 игроков, которые принесут мне наибольшее количество очков в пределах максимальной зарплаты.

Например, представьте, что исходные данные состоят из

1. Имя игрока
2. Позиция (нападающий, защитники, вратарь)
3. Прогнозируемое количество очков на этот сезон
4. Заработная плата.

Теперь мне нужны 20 игроков, которые принесут мне наибольшее количество очков в пределах X зарплат. Позже, на втором этапе, я хотел бы сделать то же самое, но в данном случае мне нужны только 12 нападающих, 6 защитников и 2 вратаря.

Теперь очевидный способ - просто использовать все возможные комбинации, однако, хотя это сработает, это недопустимый вариант, так как с 500 игроками это будет иметь слишком много возможных комбинаций.Я мог бы добавить несколько умных фильтров, чтобы сократить 500 игроков до 50 лучших нападающих, 30 лучших защитников и 15 лучших вратарей, но, тем не менее, это будет очень медленный процесс.

Мне интересно, есть ли другие алгоритмы для реализации этого. Это просто для развлечения, а не для важного делового запроса. Но если у вас есть какие-то мысли о том, как действовать дальше, дайте мне знать.

Моя первая попытка заключалась в использовании алгоритма ранца с некоторой помощью из других источников. Кажется, работает только с зарплатой в качестве параметра. Я изо всех сил пытаюсь понять, как добавить параметр команды из 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;
}

} 
}

Спасибо за вашу помощь!