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

Question

<分区>

Answer 1

首先很容易看出问题的泛化是NP-Hard ，并且可以立即从 Knapsack Problem 减少:

给定一个背包问题:weight=W, costs_of_items=C, weight_of_items=X，将问题简化为不限制玩家数量的问题(一般化最多k 个玩家，其中 k 由您选择)。

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

但是，我们可以根据 knapsack pseudo-polynomial solution 开发一个解决方案.
为简单起见，假设我们只对小前锋的数量进行限制(可以应用答案的原则来增加更多的限制)。

那么，这个问题可以用下面的递归方法来解决:

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 = 可供选择的玩家数量

---

如果您发现最佳解决方案太耗时，我建议您选择启发式解决方案，例如hill climbing或 Genetic Algorithms ，它将尽可能地优化结果，但不能保证找到全局最大值。