Pythonで指定されたサーバーコアですべてのタスクを実行できるか判定する方法

2つのリスト cores と tasks があるとします。cores[i] は i 番目のサーバーで利用可能なコア数を表し、tasks[i] はそのタスクの実行に必要なコア数を表します。各タスクは必ず1台のサーバーでのみ実行されなければならず、1台のサーバーが複数のタスクを担当することも許容されます。ここでの目的は、与えられたコア数ですべてのタスクを実行できるかどうかを判定することです。

たとえば、入力が cores = [10, 7]、tasks = [7, 3, 2, 2, 1] の場合、出力は True になります。これは、tasks[0](7)と tasks[1](3)をコア数10の最初のサーバーに割り当て、残りのタスク(2、2、1)をコア数7の2番目のサーバーに割り当てることができるためです。

解決アプローチ:バックトラッキング

この問題は「バックトラッキング(探索の巻き戻し)」によって効率的に解けます。基本的な考え方は、各タスクを順番に取り出し、割り当て可能なすべてのサーバーを順に試すというものです。ある割り当てで先に進めなくなった場合は、直前の割り当てを取り消して別のサーバーを試します。

具体的な手順は以下の通りです。

1. 関数 solve() を定義します。引数として cores と tasks を受け取ります。
2. tasks が空になった場合は True を返します(すべてのタスクの割り当てに成功したことを意味します)。
3. i を 0 から cores のサイズ - 1 まで繰り返します。
   • cores[i] >= tasks[0] であれば、cores[i] から tasks[0] を差し引きます。
   • solve(cores, 残りのタスクリスト) が True を返せば、そのまま True を返します。
   • 失敗した場合は cores[i] に tasks[0] を戻し(バックトラック)、次のサーバーを試します。
4. どのサーバーにも割り当てられなかった場合は False を返します。

実装例

以下のPythonコードで実際の動作を確認できます。

def solve(cores, tasks):
    if not tasks:
        return True

    for i in range(len(cores)):
        if cores[i] >= tasks[0]:
            cores[i] -= tasks[0]
            if solve(cores, tasks[1:]):
                return True
            cores[i] += tasks[0]
    return False

cores = [10, 7]
tasks = [7, 3, 2, 2, 1]
print(solve(cores, tasks))

入力

[10, 7], [7, 3, 2, 2, 1]

出力

True

計算量について

このアルゴリズムの最悪計算量は、タスク数を n、サーバー数を m とすると O(m^n) になります。各タスクに対して最大 m 通りのサーバー選択肢があるためです。ただし、コア数の制約によって多くの分岐が早期に枝刈りされるため、実際の入力では高速に動作することが多いです。タスクを降順にソートしてから探索を開始すると、大きなタスクが先に処理されて枝刈りが早まり、さらに効率が向上します。