重み付きジョブスケジューリング：動的計画法で最大利益を求める方法

開始時刻・終了時刻・利益が与えられた複数のジョブの中から、互いに時間帯が重ならないジョブの組み合わせを選び、合計利益を最大化するのが「重み付きジョブスケジューリング」問題です。

このアルゴリズムでは動的計画法（DP）を活用し、テーブルに部分問題の結果を保存しながら、ボトムアップ方式で全体の問題を解いていきます。

基本的な実装での計算量は O(n²) ですが、二分探索を使って競合しないジョブを検索することで、O(n log n) まで高速化することも可能です。

アルゴリズムの考え方

各ジョブについて「そのジョブを採用する場合」と「採用しない場合」の利益を比較し、大きい方をテーブルに記録します。あらかじめジョブを終了時刻の昇順にソートしておくことで、現在のジョブと競合しない直前のジョブを効率よく見つけられるのがポイントです。

入力と出力

Input:
ジョブの開始時刻、終了時刻、利益を行列形式で与えます。ここでは4つのジョブがあります。
3   5  25
1   2  50
6  15  75
2 100 100

Output:
最大利益は150。
ジョブの選択順序は job 2 → job 4、または job 2 → job 1 → job 3。どちらの場合も最大利益は150になります。

アルゴリズム

findMaxProfit(jobList, n)

入力： ジョブのリストとジョブ数

出力： ジョブから得られる最大利益

Begin
    sort job list according to their ending time
    define table to store results
    table[0] := jobList[0].profit

    for i := 1 to n-1, do
       addProfit := jobList[i].profit
       nonConflict := find jobs which is not conflicting with others
       if any non-conflicting job found, then
          addProfit := addProfit + table[nonConflict]
       if addProfit > table[i - 1], then
          table[i] := addProfit
       else
          table[i] := table[i-1]
    done
    result := table[n-1]
    return result
End

C++による実装例

#include <iostream>
#include <algorithm>
using namespace std;

struct Job {
    int start, end, profit;
};

bool comp(Job job1, Job job2) {
    return (job1.end < job2.end);
}

int nonConflictJob(Job jobList[], int i) {       //jobList[i]と競合しないジョブを探す
    for (int j=i-1; j>=0; j--) {
       if (jobList[j].end <= jobList[i-1].start)
          return j;
    }
    return -1;
}

int findMaxProfit(Job jobList[], int n) {
    sort(jobList, jobList+n, comp);           //終了時刻を基準にジョブをソート

    int *table = new int[n];       //結果保存用のテーブルを作成
    table[0] = jobList[0].profit;

    for (int i=1; i<n; i++) {
       // 現在のジョブを含めた場合の利益を計算
       int addProfit = jobList[i].profit;
       int l = nonConflictJob(jobList, i);
       if (l != -1)
          addProfit += table[l];
       table[i] = (addProfit>table[i-1])?addProfit:table[i-1];       //最大値を求める
    }

    int result = table[n-1];
    delete[] table;                 //メモリからテーブルを解放
    return result;
}

int main() {
    Job jobList[] = {
       {3, 5, 25},
       {1, 2, 50},
       {6, 15, 75},
       {2, 100, 100}
    };

    int n = 4;
    cout << "The maximum profit: " << findMaxProfit(jobList, n);
    return 0;
}

出力結果

The maximum profit: 150