在C ++中查找与加权作业计划有关的作业

假设我们有一个N个作业的列表，其中每个作业都有三个参数。1.开始时间2.结束时间3.利润我们必须找到一个与最大利润相关的工作子集，以便该子集中没有两个工作重叠。

因此，如果输入像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

• 而左<=右，则执行-

• 右：=中-1

• 如果Jobs [mid + 1] .finish <= Jobs [index] .start，则-

• 返回中

• 左：=中+ 1

• 返回中

• 中：=（左+右）/ 2

• 如果Jobs [mid] .finish <= Jobs [index] .start，则-

• 除此以外

• 返回-1

• 从主要方法中，执行以下操作-

• 根据完成时间对数组job_list进行排序

• 为工作表创建一个大小为n的表

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

• 在表[0]的末尾插入job_list [0]

• 对于初始化i：= 1，当i <n时，更新（将i增加1），-

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

• table [i] .value：= include_profit

• table [i] .job：= table [l] .job

• 在表[i]的末尾插入job_list [i]

• include_profit：= include_profit + table [l] .value

• include_profit：= job_list [i] .profit

• l：= find_no_conflict(job_list,i)

• 如果l不等于-1，则-

• 如果include_profit> table [i-1] .value，则-

• 除此以外

• 显示表格中的作业

• 显示最佳利润：= 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