Đây là một dự án thú vị nhỏ mà tôi đã bắt đầu thử và tối đa hóa cơ hội chiến thắng trong hồ bơi hockey văn phòng của chúng tôi. Tôi đang cố gắng tìm cách tốt nhất để chọn 20 người chơi sẽ cho tôi nhiều điểm nhất trong giới hạn mức lương tối đa.Hockey pool Algorithm
Ví dụ, hãy tưởng tượng rằng các dữ liệu thô được làm bằng
- Các Tên cầu thủ
- Chức vụ (Forward, thủ phòng vệ, Goalie)
- lượng dự đoán điểm cho mùa này
- Lương.
Bây giờ tôi muốn 20 người chơi sẽ cho tôi điểm cao nhất trong giới hạn mức lương X. Sau đó, như một giai đoạn 2, tôi muốn làm điều tương tự tuy nhiên trong trường hợp này, tôi chỉ muốn 12 tiền đạo, 6 vệ sĩ và 2 thủ môn. Bây giờ cách rõ ràng là chỉ cần đi mọi kết hợp có thể, tuy nhiên trong khi điều này sẽ làm việc nó không phải là một lựa chọn hợp lệ như với 500 người chơi, điều này sẽ có quá nhiều sự kết hợp có thể. Tôi có thể thêm một số bộ lọc thông minh để giảm 500 người chơi trong top 50 trở đi, top 30 người bảo vệ và 15 thủ môn hàng đầu nhưng vẫn, đây sẽ là một quá trình rất chậm.
Tôi tự hỏi nếu có các thuật toán khác để thực hiện điều này. Đây chỉ là cho vui và không phải là một yêu cầu kinh doanh quan trọng. Nhưng nếu bạn có một số suy nghĩ về cách tiến hành, vui lòng cho tôi biết.
Lần thử đầu tiên của tôi là sử dụng thuật toán ba lô với một số trợ giúp từ các nguồn khác. Dường như chỉ làm việc với mức lương như một tham số. Tôi đang đấu tranh để tìm ra cách thêm tham số đội 20 cầu thủ. Của nó trong. Net nhưng nên dễ dàng để chuyển đổi sang Java.
Tôi đã nghĩ đến việc thực hiện một vòng lặp riêng biệt để tìm ra các đội tốt nhất với 20 người chơi không có tiền lương và sau đó so sánh hai danh sách cho đến khi tôi tìm thấy đội cao nhất trong hai danh sách. Không chắc.
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;
}
}
}
Cảm ơn sự giúp đỡ của bạn!
Đối với giai đoạn 1, bạn không quan tâm đến vị trí nào cả? Ví dụ, bạn không muốn có ít nhất một thủ môn? –