我有500个花车的清单.
我想从列表中挑选出11个数字,这些数字加在一起时总和为N,N在X< = N< = Y的范围内 这基本上是为了一个梦幻足球比赛,我们在人员阵容中自动选出11名球员. 总成本应该在一个范围内,而不是随机的. 一个解决方案可能是连续随机挑选11名玩家,直到我得到一个符合范围的总数,但我想知道是否有更优雅的方法？
最佳答案
就像评论者指出的那样,这是一个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作为每次选择的最小/最大元素.这应该会使算法变得更快,但它也会导致选择较少的“随机”选择.