私は次の問題を抱えています (私のバージョンでは、おそらく問題を解決しやすくするいくつかの制約がありますが、一般的な解決策も良いでしょう):
10 エントリの 4 つのリストがあります。最初のリストには 0 ～ 6 の整数エントリが含まれ、他の 3 つのリストには 0 ～ 3 のエントリが含まれます。これら 4 つのリストの要素の最適な組み合わせを 100 個見つける必要があります。1 つの組み合わせは、各リストから 1 つずつ、4 つの値の合計で構成されます。結果の要素の値を知る必要があるだけでなく、それらがどのように構成されたかについても知る必要があることに注意してください。値に関連する情報は他にもあるからです。
例 1:
list A: 6, 3, 2, 2, 1, 0, 0, 0, 0
list B: 3, 2, 0, 0, 0, 0, 0, 0, 0
list C: 2, 2, 0, 0, 0, 0, 0, 0, 0
list D: 3, 1, 1, 1, 1, 1, 0, 0, 0
この場合、5 つの最適な組み合わせは次のようになります。
- 14 (A[0] + B[0] + C[0] + D[0])
- 14 (A[0] + B[0] + C[1] + D[0])
- 13 (A[0] + B[1] + C[0] + D[0])
- 13 (A[0] + B[1] + C[1] + D[0])
- 12 (A[0] + B[0] + C[0] + D[1])
これはおそらく、この問題を解決するほとんどのアルゴリズムの最初のステップになるため、リストのエントリを並べ替えたことに注意してください。
些細な解決策
最も簡単な解決策は、10,000 通りの可能な組み合わせをすべて形成し、その中から 100 のベストを選択することです。10,000 の可能な組み合わせを並べ替える必要さえありません。最初に配列をスキャンして、どの値がどのくらいの頻度で表示されるかを分析できます。次に、次の値のスキャンで 100 の最良の値 (およびそれらのさらなる属性) を選択できます。
うまくいかない解決策
私の頭に浮かんだ別のアイデアは次のとおりです。まず、リストをソートする必要があります。各リストで、ソリューションに貢献できるエントリとそうでないエントリを区切るインデックスを見つけたいと思います。例 1 で 4 つの最適な組み合わせを見つけなければならない場合、たとえば、リストBとの最初の 2 つの要素を選択し、リストとの最初の要素を選択するCと、次の結果
が得られます。AD
A: 6
B: 3, 2
C: 3, 2
D: 3
これらのサブリストのすべての組み合わせにより、最適なソリューションが得られます。ただし、次の例に示すように、これが常に可能であるとは限りません。
例 2:
（今回は2つのリストのみ）
list A: 6, 5, 5, 0, 0, ...
list B: 3, 1, 1, 0, 0, ...
ここで、最良の 4 つのソリューションは次のとおりです。
- 6 + 3
- 5 + 3
- 5 + 3
- 6 + 1
ただし、この解決策は、他のすべての組み合わせから 4 つの組み合わせを分離するインデックスでは見つかりません。