Questo è un piccolo progetto divertente che ho iniziato a provare e massimizzare le mie possibilità di vincere il nostro pool di hockey in ufficio. Sto cercando di trovare il modo migliore per selezionare 20 giocatori che mi daranno il maggior numero di punti in un tetto massimo di stipendio.Algoritmo per piscina da hockey
Ad esempio, immaginiamo che i dati grezzi è fatta di
- il nome del giocatore
- posizione (avanti, Difensori, Portiere)
- prevista quantità di punti per questa stagione
- Stipendio.
Ora voglio i 20 giocatori che mi daranno il maggior numero di punti entro lo stipendio X cap. Più avanti, come fase 2, vorrei fare la stessa cosa però in questo caso, voglio solo 12 attaccanti, 6 difensori e 2 portiere.
Ora, il modo più ovvio è di fare semplicemente tutte le combinazioni possibili, tuttavia mentre questo funzionerà non è un'opzione valida come con 500 giocatori, questo avrebbe troppe combinazioni possibili. Potrei aggiungere alcuni filtri intelligenti per ridurre i 500 giocatori ai primi 50 attaccanti, i primi 30 difensori e i primi 15 portieri, ma comunque, sarebbe un processo molto lento.
Mi chiedo se ci sono altri algoritmi là fuori per implementare questo. Questo è solo per divertimento e non è una richiesta commerciale importante. Ma se hai qualche idea su come procedere, faccelo sapere.
Il mio primo tentativo è stato l'utilizzo dell'algoritmo dello zaino con l'aiuto di altre fonti. Sembra che funzioni solo con lo stipendio come parametro. Sto cercando di capire come aggiungere il parametro del team di 20 giocatori. È in. Net ma dovrebbe essere facile da convertire in Java.
Stavo pensando di fare un ciclo separato per capire le migliori squadre con 20 giocatori senza regoaglia di stipendio e quindi confrontare i due elenchi finché non trovo la squadra più alta nella lista due. Non sono sicuro.
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;
}
}
}
Grazie per il vostro aiuto!
Per la fase 1 non ti interessa affatto le posizioni? Ad esempio, non vuoi almeno un portiere? –