幻想足球优化算法的思路

Question

所以,这与标准的梦幻足球有点不同.我所拥有的是球员名单,他们的平均"每场比赛得分"(PPG)和他们的薪水.我想在我的球队没有超过工资帽的限制下最大化每场比赛得分.一个团队由1个QB,1个TE,3个WR和2个RB组成.所以,如果我们有15个每个位置,我们有15X15 X(15 c 3)X(15 c 2)= 10749375个可能的团队.

漂亮的计算复杂.我可以使用一些分支和绑定,即一旦团队超过工资帽我可以修剪树,但即使这样算法仍然很慢.我尝试了另一个选项,我使用了一个"遗传算法",即制作了10个随机团队,选择了最好的一个团队并"突变"它(随机改变一些玩家)进入另外10个团队,然后选择那些然后通过一堆循环直到"最佳阵容"的每场比赛停止变得更好的时间.

必须有更好的方法来做到这一点.我不是计算机科学家,我只参加过算法学的入门课程.程序员 - 你有什么想法？我觉得动态编程的某种应用可能会有所帮助.

谢谢

Answer 1

取i为n名球员中当前的球员人数，j为当前剩余的工资。取 m[i, j] 为动态解集。

Then m[i, 0] = 0, m[0, j] = 0
and

m[i, j] = m[i - 1, j] if salary for player i is greater than j

else

m[i, j] = max ( m[i - 1, j], m[i - 1, j - salary of player i] + PPG of player i)

抱歉，我不懂 R，但我很擅长算法，所以我希望这会有所帮助。

您可以进行的进一步优化是，您实际上只需要 2 行 m[i, j]，因为 DP 解决方案仅使用当前行和最后一行（这样可以节省内存）