自动选取11名球员在一个幻想足球阵容，其中总价格接近N

Question

我有500个花车的清单。在

我想从列表中选出11个数字，它们加起来等于N，N在X<；=N<；=Y范围内

它基本上是为了一场梦幻足球赛，我们自动选择11名球员在个人阵容。在

总成本应该在某个范围内，而不是随机的。在

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

Answer 1

什么是X和Y？你能用整数来近似他们和玩家的分数吗？ 如果是这样的话，那么您可以使用类似for的动态编程 knapsack problem。在

但是有几个问题。在

1. 该算法需要O（Y）内存和O（M+Y）时间，其中M是玩家总数。在
2. 如果你想找到所有允许的团队，然后随机选择一个，那么你会有一个问题，这类团队的数量可能是指数级的。在

所以，对于实际的方法，我投票支持mrip的建议。在

Answer 2

我认为这不是最好的方法，但可能会奏效：

import random

data  # list of 500 floats
n = 11 # numbers to pick
bottom_limit = X
top_limit = Y
max_tries = 100

data_min = min(data)
data_max = max(data)

i = 0
while i < max_tries:
    i += 1
    picked = []

    for j in xrange(n-1):  # pick random except the last one
        picked.append(random.choice(data))
    s = sum(picked)

    if s + data_min < top_limit and s + data_max > bottom_limit:
        # Ok, we know we can find proper values, let's do it
        filtered = []
        for value in data:
            if value + s > bottom_limit and value + s < top_limit:
                filtered.append()

        picked.append(random.choice(filtered))
        break  # Success
else:
    print 'Unable to pick, sorry'

成功率与数据和极限值高度相关。在

希望这有帮助。在

Answer 3

正如评论家指出的，这是一个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中最小/最大的元素。这会使算法运行得更快，但也会减少对选择的“随机”选择。在