这是一个有趣的项目,我已经开始尝试并最大化我赢得办公室曲棍球池的机会.我正在努力寻找最佳方式来选出20名球员,这些球员将在最高工资帽中给予我最高分.
例如,假设原始数据是由
现在我希望20名球员能够在X工资帽中获得最高分.后来,作为第2阶段,我想做同样的事情但是在这种情况下,我只想要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;
}
}
}
谢谢你的帮助!
不幸的是，你不应该期望找到一个好的解决方案来解决这个问题，因为它是NP-hard 的。除非P = NP，否则不存在任何多项式时间算法，并且穷举搜索可能是最好的算法之一（尽管您可以使用一些启发式方法来加速）。
为了看出这个问题是 NP 困难的，我们将展示如何在多项式时间内将背包问题简化为该问题。给定由集合 S = {(权重1 , 值1 ), (权重2 , 值2 ), ... , (权重n , 值n )} 和权重限制 k 组成的子集和问题的任何实例，我们可以通过创建一组球员来构建曲棍球问题的实例，这些球员的薪水是权重，预期得分是值。然后，我们尝试找到工资不超过 k 的球员的最大体重组合，该组合与您在原始背包问题中可以赚到的不超过目标体重的最大总和相同。
不过，正如您发布的代码所示，有一个伪多项式时间算法可以解决背包问题。假设工资很低（或者您可以将其标准化为较小的数字），您也许可以利用它取得良好的效果。
虽然是否存在多项式时间算法来获得准确答案值得怀疑，但如果您可以接受近似最优解，则可以使用多项式时间算法来近似解决背包问题。有关详细信息，请查看这些注释，其中详细介绍了两种算法。有趣的是，它们依赖于您似乎正在使用的伪多项式时间算法，所以也许它们很容易实现？
抱歉，让你对数学一个好的解决方案的希望破灭了……NP 难题往往会这样做。:-(