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

• 왼쪽 <=오른쪽 동안 −

  • 중간 :=(왼쪽 + 오른쪽) / 2

  • job[mid].finish <=jobs[index].start이면 -

    • 작업[mid + 1].finish <=작업[index].start이면 -

      • 왼쪽 :=중간 + 1

    • 중간 반환

      • 중간 반환

  • 그렇지 않으면

    • 오른쪽 :=중간 - 1

• 반환 -1

• 기본 방법에서 다음을 수행하십시오 -

• 완료 시간에 따라 배열 job_list 정렬

• 크기가 n인 테이블이라는 작업에 대한 테이블을 만듭니다.

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

• 테이블[0]의 끝에 job_list[0] 삽입

• initialize i :=1의 경우, i

  • include_profit :=job_list[i].profit

  • l :=find_no_conflict(작업 목록, i)

  • l이 -1과 같지 않으면 -

    • include_profit :=include_profit + 테이블[l].value

  • include_profit> table[i - 1].value이면 -

    • table[i].value :=include_profit

    • 테이블[i].작업 :=테이블[l].작업

    • 테이블[i]의 끝에 job_list[i] 삽입

  • 그렇지 않으면

    • 테이블[i] :=테이블[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