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，附加條件

回答

相關問題