Pythonで学ぶ課題スケジューリング問題：動的計画法で獲得単位を最大化する方法

問題概要

同じ長さを持つ3つのリスト「deadlines（締め切り）」「credits（単位）」「durations（所要日数）」があるとします。これらは講義の課題に関する情報を表しています。i番目の課題については、deadlines[i]が締め切り日、credits[i]がその課題で得られる単位数、durations[i]が完了までにかかる日数を示します。

この問題には以下の制約があります。

• 1つの課題が完了してからでなければ、次の課題に取り掛かれない
• 締め切り当日に課題を完了することも可能
• 現在は0日目の始まりである

例えば、入力が deadlines = [7, 5, 10]、credits = [8, 7, 10]、durations = [5, 4, 10] の場合、出力は 10 となります。

解法のアプローチ

この問題は動的計画法（DP）を用いて効率的に解くことができます。基本的な考え方は、「各課題に対して『取り組む』か『スキップする』かを選択し、締め切りに間に合う場合のみ単位を加算する」というものです。課題を締め切りの早い順にソートしておくことで、スケジュールの判定がシンプルになります。

具体的には、以下の手順で解きます。

1. jobs := zip(deadlines, durations, credits) を作成し、ソートする
2. 再帰関数 dp() を定義する
   • i が jobs のサイズ以上になったら 0 を返す（ベースケース）
3. ans := dp(i + 1, day) — 現在の課題をスキップする場合の結果
4. deadline, duration, credit := jobs[i] として現在の課題情報を取り出す
5. day + duration − 1 ≤ deadline（締め切りに間に合う）の場合：
   • ans := ans と dp(i + 1, day + duration) + credit の最大値 — 課題に取り組む場合の結果と比較
6. ans を返す
7. メイン処理から dp(0, 0) を呼び出して結果を得る

実装例

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

class Solution:
    def solve(self, deadlines, credits, durations):
        jobs = sorted(zip(deadlines, durations, credits))
        def dp(i=0, day=0):
            if i >= len(jobs):
                return 0
            ans = dp(i + 1, day)
            deadline, duration, credit = jobs[i]
            if day + duration - 1 <= deadline:
                ans = max(ans, dp(i + 1, day + duration) + credit)
            return ans
        return dp()

ob = Solution()
deadlines = [7, 5, 10]
credits = [8, 7, 10]
durations = [5, 4, 10]
print(ob.solve(deadlines, credits, durations))

入力

[7, 5, 10], [8, 7, 10], [5, 4, 10]

出力

10

コードのポイント

この実装では、dp関数が「i番目以降の課題をday日目から処理するときに得られる最大単位数」を返します。各課題について、スキップする場合と取り組む場合の両方を試し、より大きい方を採用することで最適解を導きます。計算量は課題数をNとするとO(2^N)ですが、メモ化（lru_cacheなど）を追加すればO(N²)程度まで改善できます。実際の入力例では、3番目の課題（締め切り10日・所要10日・単位10）を0日目から開始することで、単位10を獲得できることが分かります。