算法与最高分，但与给定的开销来选择球员 [英] Algorithm to select Player with max points but with a given cost

问题描述

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

I need a algorithm that does the following:

在NBA的梦幻联赛，因为：

In an NBA fantasy league, given:

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

选择最佳的9玩家阵容。

Select the optimal 9-player line-up.

要使用一个简单的例子，说有只有四个球员在联赛中，你有$ 10,000的工资帽，并且希望最佳（意为最高分）3-球员阵容。这里有平均点总数和价格：

To use an easy example, say there are only four players in the league, you have a $10,000 salary cap, and you want the optimal (meaning maximum points) 3-player lineup. Here are there average point totals and prices:

勒布朗·詹姆斯：30分/游戏; $ 5,000个
科比：25分/游戏; $ 3,500名
德隆 - 威廉姆斯20分/游戏; $ 2,500个
谢尔文 - 麦克：15分/游戏; 2000 $

Lebron James: 30 points/game; $5,000
Kobe Bryant: 25 points/game; $3,500
Deron Williams: 20 points/game; $2,500
Shelvin Mack: 15 points/game; $2,000

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

The optimal lineup would be Bryant, Williams and Mack, which would cost $8,000 and score 60 points.

还有一个另外的约束：该程序必须选择一定数量的队员每个位置（例如，两个控球后卫，两名得分后卫，两名小前锋，二前锋和一个中心）。这是什么使设计程序难度。

There is one further constraint: the program must select a certain number of players for each position (e.g., two point guards, two shooting guards, two small forwards, two power forwards and one center). This is what makes designing the program difficult.

推荐答案

首先，很容易看出问题的概括是的 NP难和距离背包问题<瞬间reduceable /一>：

First, it is easy to see that the generalization of the problem is NP-Hard, and is instantly reduceable from the Knapsack Problem:

给出一个背包问题：重量= W，costs_of_items = C，weight_of_items = X ，减少的问题这个问题上的玩家数量没有限制（泛化将至多 K 的球员，其中 K 选择您所）。

Given a knapsack problem: weight=W, costs_of_items=C, weight_of_items=X, reduce the problem to this problem with no restrictions on the number of players (the generalization would be at most k players, where k is chosen by you).

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

So, we can conclude there is no known polynomial time solution to the problem.

不过，我们可以开发基于背包伪多项式解决方案的一个解决方案。
为简单起见，假设我们有限制仅在小前锋的号码（可用于答案的原则，以增加更多的限制）。

But, we can develop a solution based on the knapsack pseudo-polynomial solution.
For simplicity, let's say we have restriction only on the number of small forwards (the principles of the answer can be applied to add more restrictions).

然后，这个问题可以用下面的递归方法来解决：

Then, the problem can be solved with the following recursive approach:

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 （无效解）

The base will be all zeros where one of the dimensions is zero: f(0,_,_)=f(_,0,_)=0 (same as regular knapsack) and f(_,_,-1)=-infnity (invalid solution)

答案将是 F（2，W，N）（2前锋的号码，如果是不同的，应当改变为好）。 是W 是工资帽和 N 是球员的数量。

The answer will be f(2,W,n) (2 for the number of forwards, if it is different, that should be changed as well). W is the salary cap and n is the number of players.

该DP解决方案将填补矩阵再presenting递归自下而上得到一个伪多项式时间的解决方案（这是伪多项式只有当限制是不变的）。

The DP solution will fill the matrix representing the recursion bottom-up to get a pseudo-polynomial time solution (It is pseudo polynomial only if the restrictions are constant).

通过重复这个过程，和添加尺寸为每个标准后，这一问题将得到最佳的解决方案，DP解决了。

By repeating the process, and adding a dimension to each criteria, this problem will be solved optimally by the DP solution.

在你将得到的复杂性是 0（B ^ P * W * N） - 其中：
B 是分支因素 - 每个位置的球员+ 1（用于零）在您的案件 B = 3号。
是W =工资帽
N =玩家人数从

The complexity you will get is O(B^p * W * n) - where:
B is the "branch factor" - the number of players per position+1 (for the zero) in your case B=3.
W = salary cap
n = number of players to select from

如果您找到最佳的解决方案太耗时，我建议去为启发式解决方案等的爬坡或遗传算法，这将尝试优化结果尽可能多的，因为他们可以，但不能保证找到一个全球性的最大值。

If you find the optimal solution too time consuming, I'd suggest going for heuristic solutions, such as hill climbing or Genetic Algorithms, which will try to optimize the result as much as they can, but are not guaranteed to find a global maxima.

这篇关于算法与最高分，但与给定的开销来选择球员的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！