c++ - 100选10，附加条件

Question

我已经开始了一个小项目来尝试学习一些新概念(希望是 C++ 或 Python)，我只是希望在我的想法开始时得到一点帮助。

*这一切都与一个更大的梦幻篮球项目有关，但我必须从某个地方开始。

我想要 100 个变量(玩家)并找到 10 个满足另一个条件的每个组合。

例如；我有 100 名球员，我想知道有多少 10 人的组合(没有重复，顺序无关紧要(所以 ABC == CBA))，将结合某个值(10 人之间的 170 分)或更高。

我假设有一个 Python 库可以为我发挥这种魔力(我很想知道)，但实际上，我更感兴趣的是如何使用 C++ 实现这一点。

感谢您的任何回复。

Answer 1

这是一些伪代码

function player_combos(array players, int minimum_total) {
  array result = []
  players = sort(players, metric=most points first)
  int total = 0
  for p1 in 0 .. length(players) {
    if players[p1].points*10 < minimum_total - total:
      break
    total += players[p1].points
    for p2 in p1+1 .. length(players) {
      if players[p2].points*9 < minimum_total - total:
        break
      total += players[p2].points
      for p3 in p2+1 .. length(players) {
        if players[p3].points*8 < minimum_total - total:
          break
        total += players[p3].points
        # continue these nested loops up to p10
        ...
                    for p10 in p9+1 .. length(players):
                      if players[p10].points < mininum_total - total:
                        break
                      # this is a valid combination
                      result.append((p1, p2, p3, p4, p5, p6, p7, p8, p9, p10))
        ...
        # remember to decrement total when we finish a loop iteration
        total -= players[p3].points
      }
      total -= players[p2].points
    }
    total -= players[p1].points
  }
  return result
}

这里的想法是，因为您首先对玩家进行排序，所以在遍历列表中的玩家时的任何时候，之后的所有玩家的总分必须等于或低于当前玩家的总分。如果当前玩家的点数乘以团队中剩余的点数小于满足最小值所需的点数，这允许您跳出当前循环。

例如，假设到目前为止您的团队中有四名球员总共获得 80 分，这意味着您还剩下 90 分才能达到最低分，还剩下 6 个名额。你的下一个玩家可以拥有的绝对最小点数是 15(因为 90/6 == 15)，所以一旦你在下一个循环中遇到一个拥有 14 点或更少点数的玩家，你就可以打破那个循环。

只要您的 minimum_total 指标设置得足够高，这应该会大大减少您需要获得的组合总数。