หางานที่เกี่ยวข้องกับการจัดตารางงานแบบถ่วงน้ำหนักใน 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

  • ถ้า jobs[mid].finish <=jobs[index].start แล้ว −

    • ถ้า job[mid + 1].finish <=jobs[index].start แล้ว −

      • ซ้าย :=กลาง + 1

    • คืนกลาง

      • คืนกลาง

  • มิฉะนั้น

    • ขวา :=กลาง - 1

• กลับ -1

• จากวิธีหลัก ให้ทำดังนี้ −

• จัดเรียงอาร์เรย์ job_list ตามเวลาที่เสร็จสิ้น

• ทำตารางสำหรับงานที่เรียกว่า table of size n

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

• แทรก job_list[0] ที่ท้ายตาราง[0]

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน

  • include_profit :=job_list[i].profit

  • l :=find_no_conflict(job_list, i)

  • ถ้า l ไม่เท่ากับ - 1 แล้ว −

    • include_profit :=include_profit + ตาราง[l].value

  • ถ้า include_profit> table[i - 1].value แล้ว −

    • table[i].value :=include_profit

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

    • แทรก job_list[i] ที่ท้ายตาราง[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