在总价格接近N的梦幻足球阵容中自动挑选11名球员的算法

Question

我有500个花车的清单.

我想从列表中选出11个数字,当加在一起时总和为N,N在一个范围内X <= N <= Y

这基本上是为了一个梦幻足球比赛,我们在人员阵容中自动选出11名球员.

总成本应该在一个范围内,而不是随机的.

一个解决方案可能是连续随机挑选11名玩家,直到我得到一个符合范围的总数,但我想知道是否有更优雅的方法？

Answer 1

正如评论者指出的那样，这是一个 NP 难题。但是，如果您的数据不太糟糕，那么以下内容应该可以很好地工作：

picks[] := K numbers chosen at random from the population
While sum(picks) is not in the allowable range
  if sum(picks) < MinRange
    select an element p from picks at random
    let subpop := elements in population which are larger than p
    replace p with a random element from subpop
  if sum(picks) > MaxRange
    select an element p from picks at random
    let subpop := elements in population which are smaller than p
    replace p with a random element from subpop

这很容易编码，它将返回一个满足约束的相对随机的选择，并且不会花费太长时间，除非您确实有问题的困难实例，在这种情况下将很难找到使用任何算法的解决方案。

如果你想加快算法速度，那么你可以选择每次的p最小/最大元素。picks这应该会使算法运行得更快，但也会导致选择的“随机”性降低。