Pythonですべてのジョブを完了させる最小時間を見つけるプログラム

問題の概要

jobs という配列があり、jobs[i] は i 番目のジョブを完了するために必要な時間を表します。さらに、ジョブを割り当てられる作業者の数 k が与えられます。各ジョブは必ずちょうど1人の作業者に割り当てなければなりません。ある作業者の「作業時間」とは、その作業者に割り当てられたすべてのジョブを完了するのにかかる合計時間のことです。このとき、あらゆる割り当て方の中で最大の作業時間が最小になる値を求めます。

例えば、入力が jobs = [2,1,3,8,5]、k = 2 の場合、出力は 10 になります。次のようにジョブを割り当てられるからです。

• 作業者1：2 + 5 + 3 = 10
• 作業者2：1 + 8 = 9

この場合、最大の作業時間は 10 となります。

解法のアプローチ

この問題はバックトラッキング（全探索＋枝刈り的な再帰）を用いて解きます。大きなジョブから順に処理することで、探索の早期段階で良い上界が得られ、無駄な分岐を減らせるのがポイントです。手順は以下の通りです。

1. jobs リストを降順にソートする。
2. 先頭の k 個のジョブを assign（各作業者の現在の負荷）とする。
3. 残りのジョブを新しい jobs リストとする。
4. 関数 dp(i, assign) を定義する。
5. i が jobs のサイズと等しければ、assign の最大値を返す（すべてのジョブを割り当て終えた状態）。
6. ans を無限大で初期化する。
7. x を 0 から k-1 までループする：
   • assign のコピーを作成し、assign[x] += jobs[i] として i 番目のジョブを作業者 x に割り当てる。
   • ans = min(ans, dp(i+1, assign)) で再帰的に最適解を更新する。
   • assign[x] -= jobs[i] で状態を元に戻す（バックトラック）。
8. ans を返す。
9. メインメソッドからは dp(0, assign) を返す。

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

def solve(jobs, k):
    jobs.sort(reverse=True)
    assign = tuple(jobs[:k])
    jobs = jobs[k:]

    def dp(i, assign):
        if i == len(jobs):
            return max(assign)

        ans = float('inf')
        for x in range(k):
            assign = list(assign)
            assign[x] += jobs[i]
            ans = min(ans, dp(i+1, tuple(assign)))
            assign[x] -= jobs[i]

        return ans

    return dp(0, assign)

jobs = [2,1,3,8,5]
k = 2
print(solve(jobs, k))

入力

[2,1,3,8,5], 2

出力

10

補足：計算量について

この手法は各ジョブを k 人の作業者のいずれかに割り当てる組み合わせを試すため、最悪計算量は O(k^n) となります（n はジョブ数）。そのため、ジョブ数が多い場合はメモ化や枝刈り（現在の最大負荷が既知の最良解を超えたら探索を打ち切るなど）を組み合わせると、実行時間を大幅に短縮できます。降順ソートにより大きなジョブを先に配置することも、探索木の剪定に有効です。