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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个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

      以上是 在C ++中查找与加权作业计划有关的作业 的全部内容， 来源链接： utcz.com/z/354943.html

      回到顶部