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ポイントのチームに4人のプレイヤーがいるとしたら、90ポイント以上が残っていて残りが6ポイント残っているということです。あなたの次のプレイヤーが持つことができるポイントの絶対最小数は、90/6 ==15から15です。したがって、次のループで14ポイント以下のプレイヤーに達すると、そのループから脱出することができます。

minimum_totalのメトリックが十分に高く設定されていれば、必要な組み合わせの総数が大幅に削減されます。

Answer 2

（固定サブセットのサイズを有する）SUBSET SUMの誘導体NP完全であることが証明さによってある問題、たぶん、あなたはここに助ける見つけることができるような音：。。Optimizing subset sum implementation

Answer 3

あなたが望む属性を持つすべてのプレイヤーのリストをフィルタリングして、すべての組み合わせに対してフィルタリングされたリストをループするだけです。

単純な（深い場合）ネストループを使用できるようにする必要があります。ここで