8

这是一个有趣的项目,我已经开始尝试并最大限度地提高赢得办公室曲棍球池的机会。我正在尝试找到最好的方法来选择 20 名球员,这些球员将在最高工资帽内给我最多的分数。

例如,假设原始数据由

  1. 玩家名称
  2. 位置(前锋、后卫、守门员)
  3. 本赛季预测积分
  4. 薪水。

现在我想要在 X 工资帽内给我最高分的 20 名球员。稍后,作为第 2 阶段,我想做同样的事情,但在这种情况下,我只想要 12 名前锋、6 名后卫和 2 名守门员。

现在显而易见的方法是简单地使用所有可能的组合,但是虽然这会起作用,但它不是一个有效的选项,因为有 500 名玩家,这将有太多可能的组合。我可以添加一些智能过滤器,将 500 名球员减少到前 50 名前锋、前 30 名后卫和前 15 名守门员,但这仍然是一个非常缓慢的过程。

我想知道是否还有其他算法可以实现这一点。这只是为了好玩,而不是重要的业务请求。但是,如果您对如何进行有一些想法,请告诉我。

我的第一次尝试是在其他来源的帮助下使用背包算法。它似乎只使用薪水作为参数。我正在努力弄清楚如何添加 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;
}

} 
}

谢谢你的帮助!

4

5 回答 5

3

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

为了看到这个问题是 NP 难的,我们将展示如何在多项式时间内将背包问题简化为它。给定由集合 S = {(weight 1 , value 1 ), (weight 2 , value 2 ), ... , (weight n , value n )} 和权重限制 k组成的子集和问题的任何实例,我们可以通过创建一组球员来构建你的曲棍球问题的一个实例,他们的薪水是体重,他们的期望分数是价值。然后,我们尝试找到薪水不超过 k 的球员的最大体重组合,这与您在原始背包问题中可以得到的不超过目标体重的最大总和相同。

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

虽然不确定是否有多项式时间算法可以得到准确的答案,但如果您对近似最优解感到满意,那么可以使用多项式时间算法来逼近背包问题的解。有关详细信息,请查看这些说明,其中详细说明了两种算法。有趣的是,它们依赖于您似乎正在使用的伪多项式时间算法,所以也许它们很容易实现?

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

于 2011-09-17T02:17:23.380 回答
3

在此处输入图像描述

在图表上绘制球员,X 轴是积分,Y 轴是薪水,原点为零。右下角的球员将是理想的廉价高分球员,左上角的球员将是不理想的昂贵的低分球员,对角线上的球员将是等价的(每分成本相同)。从 X 水平逆时针到 Y 垂直扫过一个原点锚定半径,形成一个不断增长的饼图切片,直到切片内有 20 名玩家或切片内的总薪水达到上限。如果您达到 $ 上限但未达到 20 名玩家,请删除切片内的“最左上角”玩家并继续。如果你达到 20 名玩家但没有达到上限,你可以从切片中删除一个低得分者,为即将进入切片的得分较高的玩家腾出空间,这会使你的每分总成本不必要地增加,但是因为它'

于 2011-09-17T04:09:23.093 回答
2

解决这类问题的一种有趣方法是使用遗传算法。实际上,我就是为自己的曲棍球池做的!

如果你好奇的话,你可以在这里看到整个 Scala 代码,但它的核心是:

def GA(nbIter: Int, popSize: Int, tournamentSize: Int) = {
  def loop(iter: Int, pop: Seq[LineUp]): LineUp = {
    val best = pop.maxBy(_.fitness)
    println("\nBest of generation " + iter + best)
    if (iter == nbIter)
      best
    else {
      val newPop = for {
        _ ← Stream.continually()
        x = tournament(pop, tournamentSize).head
        y = (x.mutants take 5) maxBy (_.fitness)
      } yield y
      loop(iter + 1, best +: newPop.take(popSize - 1))
    }
  }
  val initialPop = LineUp.randomStream.take(popSize)
  loop(0, initialPop)
} 

它首先生成一个随机的有效阵容集合(尊重工资帽和职位限制)。对于每次迭代,它通过使用锦标赛选择爬山的组合来生成一个新的种群。“体能”被简单地定义为薪水最低的阵容作为决胜局的预期得分数。

当然,这只是一种启发式方法,但是如果您的玩家列表不是太大,并且您可以让算法运行一段时间,那么您很有可能会找到一个相当优化的解决方案。

于 2011-10-12T18:00:00.683 回答
0

问题可能很困难,但您可以利用守门员不会在进攻端打球的事实(更正式:您选择的实体属于不同类别)来改善您的运行时间。

此外,您可能希望找到问题的近似解决方案。使用该值来限制最佳解决方案并对其进行搜索。

于 2011-09-17T06:09:33.720 回答
0

您可以轻松地将其表述为 ILP。求解它们也是 NP-Hard,但问题实例似乎没有那么大,所以它可能是完美的(一个求解器是例如 lpsolve)。即使由于问题的大小而无法完美解决,ILP 也存在很好的启发式方法。

于 2011-09-17T06:28:07.873 回答