C++での加重ジョブスケジューリングに関係するジョブを検索する

各ジョブに3つのパラメーターがあるN個のジョブのリストがあるとします。 1.開始時間2.終了時間3.利益サブセット内の2つのジョブが重複しないように、最大​​利益に関連付けられたジョブのサブセットを見つける必要があります。

したがって、入力がN=4およびJ={{2、3、55}、{4、6、25}、{7、20、150}、{3、150、250}}の場合、出力は[（2、3、55）、（3、150、250）]と最適な利益305

これを解決するには、次の手順に従います-

• 関数find_no_conflict（）を定義します。これには、配列ジョブ、インデックス、

  が必要です。

• 左：=0、右：=インデックス-1

• 左<=右、実行-

  • mid：=（左+右）/ 2

  • jobs [mid] .finish <=jobs [index] .startの場合、-

    • jobs [mid + 1] .finish <=jobs [index] .startの場合、-

      • 左：=半ば+ 1

    • 途中で戻る

      • 途中で戻る

  • それ以外の場合

    • 右：=半ば-1

• -1を返す

• メインの方法から、次のようにします-

• 終了時間に基づいて配列job_listを並べ替えます

• サイズnのテーブルと呼ばれるジョブのテーブルを作成します

• table [0] .value：=job_list [0] .profit

• table [0]

  の最後にjob_list[0]を挿入します

• 初期化i：=1の場合、i

  • 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

    • table [i]

      の最後にjob_list[i]を挿入します

  • それ以外の場合

    • table [i]：=table [i-1]

• テーブルからジョブを表示する

• 最適な利益を表示する：=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