7

我需要一个执行以下操作的算法：

在 NBA 幻想联盟中，给出：

  1. 每个玩家的平均总分
  2. 每个玩家的价格
  3. 工资帽

选择最佳的 9 人阵容。

举一个简单的例子，假设联盟中只有四名球员，你有 10,000 美元的工资帽，并且你想要最佳（即最高分）三人阵容。以下是平均积分和价格：

勒布朗詹姆斯：30分/场；5000 美元的
科比·布莱恩特：25 分/场；3,500 美元
德隆威廉姆斯：20 分/场；2,500 美元
Shelvin Mack：15 分/场；2,000 美元

最佳阵容将是科比、威廉姆斯和麦克，这将花费 8,000 美元并得到 60 分。

还有一个限制：程序必须为每个位置选择一定数量的球员（例如，两名控球后卫、两名得分后卫、两名小前锋、两名大前锋和一名中锋）。这就是使程序设计变得困难的原因。

4

2 回答 2

5

首先，很容易看出问题的泛化是NP-Hard，并且可以立即从背包问题中约简：

给定一个背包问题：weight=W, costs_of_items=C, weight_of_items=X，将问题简化为这个问题，不限制玩家的数量（一般化最多是k玩家，k由你选择）。

因此，我们可以得出结论，该问题没有已知的多项式时间解。

但是，我们可以开发一个基于背包伪多项式解的解。
为简单起见，假设我们仅对小前锋的数量进行了限制（可以应用答案的原则来添加更多限制）。

然后，可以使用以下递归方法解决问题：

if i is not a forward, same as the original knapsack, while maintaining the #forwards
    f(i,points,forwards) = max {
                f(i-1,points-C[i],forwards)
                f(i-1,points,forwards)
                           }
if i is a forward:
    f(i,points,forwards) = max {
                //We used one of the forwards if we add this forward to the team
                f(i-1,points-C[i],forwards-1) 
                f(i-1,points,forwards)
                           }

基数将全为零，其中一个维度为零：（f(0,_,_)=f(_,0,_)=0与常规背包相同）和f(_,_,-1)=-infnity（无效解决方案）

答案将是f(2,W,n)（前锋数量为 2，如果不同，也应该更改）。W是工资帽，n是球员人数。

DP 解将自下而上填充表示递归的矩阵以获得伪多项式时间解（仅当限制条件不变时才为伪多项式）。

通过重复这个过程，并为每个标准添加一个维度，这个问题将通过 DP 解决方案得到最佳解决。

您将获得的复杂性是O(B^p * W * n)- 其中：
B是“分支因素” - 在您的情况下，每个位置的玩家人数+1（对于零）B=3。
W= 工资帽
n= 可供选择的球员人数

如果您发现最佳解决方案过于耗时，我建议您使用启发式解决方案，例如爬山或遗传算法，它们会尝试尽可能优化结果，但不能保证找到全局最大值。

于 2012-10-31T12:45:13.513 回答
1

使用动态规划可以轻松解决这个问题。参考这个

让f[i][j]我们用j美元与第一批i玩家一起获得的最高分，所以

f[i][j] = 最大{

  1. f[i - 1][j] //我们不选择第 i 个玩家
  2. f[i - 1][j - cost[i]] + point[i] //我们选择他

}

最后f[TOTALPLAYER][MONEYCAP]是答案。

主要思想是确定是否为每个玩家选择他。

该数组f[][]仅用于加速搜索过程。

顺便说一句，乔利特是对的。

于 2012-10-31T12:06:08.177 回答