C++で加重ジョブスケジューリング問題を解く方法:最大利益を得るジョブの組み合わせを検索

加重ジョブスケジューリング問題とは

N個のジョブのリストがあり、各ジョブには次の3つのパラメータが与えられています。

• 開始時刻(Start Time)
• 終了時刻(Finish Time)
• 利益(Profit)

求めるのは、選択したジョブ同士が時間的に重ならないという条件のもとで、合計利益が最大になるジョブの部分集合です。

たとえば、N = 4、J = {{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}} という入力が与えられた場合、出力は [(2, 3, 55),(3, 150, 250)] となり、最適な利益は 305 になります。

解法のアルゴリズム

この問題は、動的計画法(DP)と二分探索を組み合わせることで効率的に解けます。基本の発想は、各ジョブについて「そのジョブを採用する場合」と「採用しない場合」の利益を比較し、大きい方をテーブルに記録していくというものです。競合しない直前のジョブを二分探索で見つけることで、全体の計算量は O(n log n) に抑えられます。

競合しないジョブの検索(find_no_conflict)

まず、指定したジョブより前に終了している直近のジョブを二分探索で見つける関数 find_no_conflict() を定義します。引数としてジョブ配列 jobs と現在のインデックス index を受け取ります。

1. left := 0、right := index - 1 で初期化します。
2. left <= right の間、次の処理を繰り返します。
   • mid := (left + right) / 2 とします。
   • jobs[mid].finish <= jobs[index].start の場合:
     • さらに jobs[mid + 1].finish <= jobs[index].start であれば、left := mid + 1 とします。
     • そうでなければ、mid を返します。
   • それ以外の場合は、right := mid - 1 とします。
3. ループを抜けたら -1 を返します(競合しないジョブが存在しないことを意味します)。

メインの手順

1. job_list を終了時刻を基準にソートします。
2. ジョブ用のテーブル table(サイズ n)を作成します。
3. table[0].value := job_list[0].profit とします。
4. table[0] のジョブリストの末尾に job_list[0] を追加します。
5. i := 1 から n - 1 まで、以下を繰り返します。
   • include_profit := job_list[i].profit とします。
   • l := find_no_conflict(job_list, i) を計算します。
   • l が -1 でない場合は、include_profit := include_profit + table[l].value とします。
   • include_profit > table[i - 1].value の場合:
     • table[i].value := include_profit とします。
     • table[i].job := table[l].job とし、その末尾に job_list[i] を追加します。
   • そうでない場合は、table[i] := table[i - 1] とします。
6. テーブルから最終的なジョブの集合を表示します。
7. 最適な利益 := table[n - 1].value を表示します。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class Job {
    public:
        int start, finish, profit;
};
struct job_with_weight {
    vector<Job> job;
    int value;
};
bool jobComparator(Job s1, Job s2) {
    return (s1.finish < s2.finish);
}
int find_no_conflict(Job jobs[], int index) {
    int left = 0, right = index - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (jobs[mid].finish <= jobs[index].start) {
           if (jobs[mid + 1].finish <= jobs[index].start)
              left = mid + 1;
           else
              return mid;
        }
        else
            right = mid - 1;
    }
    return -1;
}
int get_max_profit(Job job_list[], int n) {
    sort(job_list, job_list + n, jobComparator);
    job_with_weight table[n];
    table[0].value = job_list[0].profit;
    table[0].job.push_back(job_list[0]);
    for (int i = 1; i < n; i++) {
       int include_profit = job_list[i].profit;
       int l = find_no_conflict(job_list, i);
       if (l != - 1)
          include_profit += table[l].value;
       if (include_profit > table[i - 1].value){
          table[i].value = include_profit;
          table[i].job = table[l].job;
          table[i].job.push_back(job_list[i]);
       }
       else
          table[i] = table[i - 1];
   }
    cout << "[";
    for (int i=0; i<table[n-1].job.size(); i++) {
       Job j = table[n-1].job[i];
       cout << "(" << j.start << ", " << j.finish << ", " << j.profit << "),";
   }
    cout << "]\nOptimal profit: " << table[n - 1].value;
}
int main() {
    Job arr[] = {{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}};
    int n = sizeof(arr)/sizeof(arr[0]);
    get_max_profit(arr, n);
}

入力

{{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}}

出力

[(2, 3, 55),(3, 150, 250)]
Optimal profit: 305