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

I need a algorithm that does the following:

在 NBA 梦幻联赛中，给出:

In an NBA fantasy league, given:

选择最佳的 9 人阵容.

Select the optimal 9-player line-up.

举一个简单的例子，假设联盟中只有四名球员，你有 10,000 美元的工资帽，并且你想要最佳(意味着最高分)的三人阵容.以下是平均总积分和价格:

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-Hard，并且可以立即从 背包问题:

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

给定一个背包问题:weight=W,cost_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:

基数将全为零，其中一个维度为零: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 解将自底向上填充表示递归的矩阵，得到伪多项式时间解(只有当约束条件不变时，它才是伪多项式).

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.

你将得到的复杂度是 O(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.