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

发布时间：2020-12-16 21:47:22 所属栏目：Python 来源：网络整理

导读：我有500个花车的清单. 我想从列表中挑选出11个数字,这些数字加在一起时总和为N,N在X 最佳答案就像评论者指出的那样,这是一个NP难问题.但是,如果您的数据不是太糟糕,以下应该可以很好地工作： picks[] := K numbers chosen at random from the populationWhi

我有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作为每次选择的最小/最大元素.这应该会使算法变得更快,但它也会导致选择较少的“随机”选择.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!