これは、オフィス ホッケー プールで優勝するチャンスを最大限にしようと始めた、ちょっとした楽しいプロジェクトです。最高サラリーキャップ内で最も多くのポイントを獲得できる 20 人の選手を選ぶ最善の方法を見つけようとしています。
たとえば、生データが
- プレイヤー名
- ポジション（フォワード、ディフェンス、ゴールキーパー）
- 今シーズンの予想ポイント数
- 給料。
X サラリー キャップ内で最も多くのポイントを獲得できる 20 人のプレーヤーが必要です。後で、フェーズ 2 として同じことをしたいと思いますが、この場合、12 人のフォワード、6 人のディフェンス、2 人のゴールキーパーだけが必要です。
明らかな方法は、考えられるすべての組み合わせを単純に実行することですが、これは機能しますが、500 人のプレイヤーの場合のように有効なオプションではありません。考えられる組み合わせが多すぎます。いくつかのスマート フィルターを追加して、500 人のプレーヤーを上位 50 人のフォワード、上位 30 人のディフェンス、上位 15 人のゴールキーパーに減らすこともできますが、それでも、これは非常に遅いプロセスになります。
これを実装する他のアルゴリズムがあるかどうか疑問に思っています。これは単なる遊びであり、重要なビジネス リクエストではありません。しかし、今後の進め方についてご意見がございましたら、お気軽にお問い合わせください。
私の最初の試みは、他の情報源からの助けを借りて、ナップザック アルゴリズムを使用することでした。パラメータとして給与だけで動作するようです。20 プレイヤーのチーム パラメータを追加する方法を理解するのに苦労しています。.Net ですが、Java に簡単に変換できるはずです。
別のループを実行して、給与に関係なく 20 人のプレーヤーで最高のチームを見つけ出し、2 つのリストで最も高いチームが見つかるまで 2 つのリストを比較することを考えていました。わからない。
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;
}
}
}
ご協力いただきありがとうございます！
