选择具有最大点但具有给定成本的玩家的算法

Question

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

在一个NBA幻想联盟中,给出:

1. 每位球员的平均得分总数
2. 每个球员的价格
3. 工资帽

选择最佳的9人阵容.

举一个简单的例子,假设联盟中只有四名球员,你有一个10,000美元的工资帽,你想要最佳(意味着最高分)3人阵容.这里有平均点总数和价格:

勒布朗詹姆斯:30分/场; $ 5,000
Kobe Bryant:25分/场; $ 3,500
德隆威廉姆斯:20分/场; $ 2,500
Shelvin Mack:场均15分; $ 2,000个

最佳阵容将是科比,威廉姆斯和麦克,这将花费8,000美元,得分为60分.

还有一个限制:程序必须为每个位置选择一定数量的球员(例如,两个控球后卫,两个得分后卫,两个小前锋,两个大前锋和一个中锋).这使得设计程序变得困难.

Answer 1

首先，很容易看出问题的泛化是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=要选择的球员人数

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

Answer 2

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

设为我们可以使用美元与第一批玩家f[i][j]获得的最大积分，所以ji

f[i][j] = 最大值{

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

}

终于f[TOTALPLAYER][MONEYCAP]是答案了。

主要思想是为每个球员决定是否选择他。

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

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