赢得签约战：用动态规划优化棒球自由球员选择策略

假设你是一支棒球大联盟球队的总经理。在寒季休季期间，你需要签入一些自由球员。球队老板给你的预算为X XX美元，你可以使用少于X XX美元来签入球员。但如果超支，球队老板就会解雇你。 　　你正在考虑在N NN个不同位置签入球员，在每个位置上，有P PP个该位置的自由球员供你选择。由于你不希望任何位置过于臃肿，因此每个位置最多签入一名球员（如果在某个特定位置上你没有签入任何球员，则意味着计划继续使用现用球员）。 　　为了确定一名球员的价值，你决定使用一种称为“VORP”或称为“球员替换价值”(Value Over Replacement Player)的统计评价指标(sabermetric)。球员的VORP值越高，其价值越高。但VORP值高的球员的签约费用并不一定比VORP值低的球员高，因此还有球员价值之外的因素影响签约费用。 　　对每个可选择的自由球员，你知道他的三方面信息： 　　• 他打哪个位置 　　• 他的签约费用 　　• 他的VORP 　　设计一个球员选择算法，使得总签约费用不超过X XX美元，而球员的总VORP值最大。