算法来选择球员，最大点，但与给定成本

我需要一个算法，执行以下操作：算法来选择球员，最大点，但与给定成本

在NBA梦幻联赛，给出：

每位玩家的平均点总
每个玩家
工资帽

价格选择最佳的9玩家阵容。要使用一个简单的例子，比如说联盟中只有四名球员，你有10,000美元的工资上限，并且你想要最优（意思是最高分数）3人球员阵容。这里有平均积分总数和价格：

勒布朗詹姆斯：30分/游戏; $ 5,000
科比 - 布莱恩特：25分/场; $ 3,500
德隆威廉姆斯：每场20分; $ 2,500
Shelvin Mack：每场15分; $ 2,000

最佳阵容将是科比，威廉姆斯和马克，这将花费8000美元和60分。还有一个限制：程序必须为每个位置（例如，两名控球后卫，两名后卫，两名小前锋，两名大前锋和一名中锋）选择一定数量的球员。这使设计程序变得困难。

来源

2012-10-31 Shakti Malik

没有最后一个约束，问题可以很容易地简化为[背包问题]（http://en.wikipedia.org/wiki/Knapsack_problem），它有一个伪多项式时间解。 – amit

詹姆斯，威廉姆斯，马克当然更好 - 9500美元，65分？ – Chowlett

每个玩家只能玩一个位置，对吧？ –

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

让f[i][j]是我们可以得到使用j美元，与第一i球员的最高分，所以

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

F [我 - 1] [J] //我们不选择第i个球员
F [I - 1] [J - 成本[I] +点[I] //我们选择他

}

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

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

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

btw，Chowlett是对的。

来源

2012-10-31 12:06:08 Topro

它没有提到：“前9名球员”和“... 2 ...的2”，算法产生的答案可能是15个便宜的，所有前锋球员，而不是9个满足限制条件的膨胀球员。我清楚地指出了与背包问题相似的地方，并且经典的解决方案还不足以作为对问题的评论。 – amit

这是问题的实质，一旦你明白这一点，就不难适应它来满足其他要求。 –

我也想要完全相同的script.If你请提供我。谢谢！ – Rahul

首先，它很容易看到问题的概括是NP-Hard，并且是从Knapsack Problem瞬间reduceable：

给定一个背包问题：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，尽可能多地尝试优化结果，但不能保证找到全局最大值。

来源

2012-10-31 12:45:13 amit

算法来选择球员，最大点，但与给定成本

回答

相关问题