knapsack-problem - 曲棍球池算法

Question

这是一个有趣的小项目，我已经开始尝试并最大限度地提高赢得办公室曲棍球池的机会。我试图找到最好的方法来选择 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;
}

} 
}

谢谢你的帮助!

Answer 1

不幸的是，您不应该期望找到解决此问题的好方法，因为它是 NP-hard .除非 P = NP ，没有任何多项式时间算法，穷举搜索可能是最好的算法之一(尽管您可能会使用一些启发式算法来加快速度)。

为了看到这个问题是 NP-hard，我们将展示如何减少 knapsack problem在多项式时间内给它。给定由集合 S = {(weight1, value1), (weight2, value2), ... , (weightn, valuen)} 和权重限制 k 组成的子集和问题的任何实例，我们可以构造一个你的曲棍球实例通过创建一组球员的问题，他们的薪水是权重，期望分数是值(value)。然后，我们尝试找到工资不超过 k 的球员的最大权重组合，这与您在原始背包问题中不超过目标权重的最大总和相同。

但是，正如您发布的代码所示，有一个伪多项式时间算法可以解决背包问题。假设薪水很低(或者您可以将它们标准化为小数字)，您可能可以使用它来获得良好的效果。

虽然不确定是否存在多项式时间算法来获得确切答案，但如果您对近似最优解没问题，那么可以使用多项式时间算法来逼近背包问题的解决方案。详情请查看 these notes ，其中详细介绍了两种算法。有趣的是，它们依赖于您似乎正在使用的伪多项式时间算法，所以也许它们很容易实现？

很抱歉让你希望用数学找到一个好的解决方案...... NP-hard 问题往往会这样做。 :-(