भारित नौकरी निर्धारण

विभिन्न कार्यों की एक सूची दी गई है, आरंभिक समय के साथ, उस कार्य के लिए समाप्ति समय और उस कार्य का लाभ भी प्रदान किया जाता है। हमारा काम नौकरियों का एक सबसेट ढूंढना है, जहां लाभ अधिकतम हो और कोई भी कार्य एक-दूसरे को ओवरलैप न कर रहा हो।

इस एल्गोरिथम में, हम उप-समस्याओं के परिणामों को संग्रहीत करने के लिए एक तालिका का उपयोग करते हैं और उप-समस्याओं के परिणामों का उपयोग करके, पूरी समस्या को नीचे-ऊपर तरीके से हल किया जा सकता है।

इस एल्गोरिथम की समय जटिलता 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