在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