การจัดตารางงานแบบถ่วงน้ำหนัก

จะมีการระบุรายการงานต่างๆ โดยจะมีการระบุเวลาเริ่มต้น เวลาสิ้นสุดและผลกำไรของงานนั้นด้วยสำหรับงานเหล่านั้น งานของเราคือค้นหาชุดย่อยของงานที่ทำกำไรสูงสุดและไม่มีงานใดทับซ้อนกัน

ในอัลกอริธึมนี้ เราใช้ตารางเพื่อเก็บผลลัพธ์ของปัญหาย่อยและการใช้ผลลัพธ์ของปัญหาย่อย ปัญหาทั้งหมดสามารถแก้ไขได้ในลักษณะจากล่างขึ้นบน

ความซับซ้อนของเวลาของอัลกอริทึมนี้คือ O(n^2) แต่เราสามารถเปลี่ยนเป็น O(n Log n) ได้โดยใช้วิธีการค้นหาแบบไบนารีเพื่อค้นหางานที่ขัดแย้งกัน

อินพุตและเอาต์พุต

Input:
The start time, finish time and profit of some jobs as matrix form. And number of jobs. Here 4 jobs are present.
3   5  25
1   2  50
6  15  75
2 100 100

Output:
The maximum profit 150.
The job sequence is job 2, job 4, or job 2, job 1, job 3. for both cases the max profit is 150 here.

อัลกอริทึม

findMaxProfit(jobList, n)

ป้อนข้อมูล: รายชื่องานและจำนวนงาน

ผลลัพธ์: กำไรสูงสุดจากงาน

Begin
   sort job list according to their ending time
   define table to store results
   table[0] := jobList[0].profit

   for i := 1 to n-1, do
      addProfit := jobList[i].profit
      nonConflict := find jobs which is not conflicting with others
      if any non-conflicting job found, then
         addProfit := addProfit + table[nonConflict]
      if addProfit > table[i - 1], then
         table[i] := addProfit
      else
         table[i] := table[i-1]
   done
   result := table[n-1]
   return result
End

ตัวอย่าง

#include <iostream>
#include <algorithm>
using namespace std;

struct Job {
   int start, end, profit;
};

bool comp(Job job1, Job job2) {
   return (job1.end < job2.end);
}

int nonConflictJob(Job jobList[], int i) {       //non conflicting job of jobList[i]
   for (int j=i-1; j>=0; j--) {
      if (jobList[j].end <= jobList[i-1].start)
         return j;
   }
   return -1;
}

int findMaxProfit(Job jobList[], int n) {
   sort(jobList, jobList+n, comp);           //sort jobs based on the ending time

   int *table = new int[n];       //create jon table
   table[0] = jobList[0].profit;

   for (int i=1; i<n; i++) {
      // Find profit including the current job
      int addProfit = jobList[i].profit;
      int l = nonConflictJob(jobList, i);
      if (l != -1)
         addProfit += table[l];
      table[i] = (addProfit>table[i-1])?addProfit:table[i-1];       //find maximum
   }

   int result = table[n-1];
   delete[] table;                 //clear table from memory
   return result;
}

int main() {
   Job jobList[] = {
      {3, 5, 25},
      {1, 2, 50},
      {6, 15, 75},
      {2, 100, 100}
   };

   int n = 4;
   cout << "The maximum profit: " << findMaxProfit(jobList, n);
   return 0;
}

ผลลัพธ์

The maximum profit: 150