100选择10，附加条件

我已经开始了一个小项目，试图学习一些新的概念（希望用C++或Python），我只是希望能够帮助我的想法开始。100选择10，附加条件

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

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

例如;我有100名球员，我想知道有多少个10的组合（没有重复和顺序无关紧要（所以ABC == CBA），会组合一个特定的值（10个之间的170个）或更高。

我假设有一个Python库来解决这个魔术对我来说（我很想知道），但实际上，我更感兴趣的是我怎么会去这个用C++。

感谢。任何反应

来源

2012-03-07 apichel

我在这里预见的问题是100选10有1.73103095×10e13的组合。如果你想要任何满足条件的10名球员，我会建议根据他们的价值对球员进行排序，并根据排名选择他们。 – twain249 2012-03-07 22:39:18

等等，你想用Python或C++来做到这一点吗？你可以在没有Python的库的情况下做到这一点，以实际学习逻辑... – 2012-03-07 22:40:18

循环所有的组合和测试是做错的方法，因为它是O（n！）@ twain249指出，这导致不切实际的迭代次数。您将需要使用动态编程以高效的方式解决此问题 – 2012-03-07 22:45:34

下面是一些伪代码

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指标设置得足够高，这应该大大减少您需要获取的组合总数。

来源

2012-03-07 23:14:19

进入这个阶段我知道这第一步会导致一些荒谬的组合。这里的最终目标是沿着这些线路运行9个不同的类别，输出每10个符合每个类别要求的玩家分组。 – apichel 2012-03-08 20:08:37

听起来像是一个SUBSET SUM衍生物（具有固定子集大小）的问题，这是被证明是NP-完整的唯一方法也许你可以在这里找到帮助：Optimizing subset sum implementation

来源

2012-03-07 22:39:39 Simon

我只是简单地用你想要的属性来过滤你的列表，然后循环遍历所有组合的过滤列表。

考虑到您的限制，您应该可以使用简单（如果深）的嵌套循环。

来源

2012-03-07 22:40:51 tletnes

100选择10，附加条件

回答

相关问题