C++ में भारित कार्य निर्धारण में शामिल नौकरियां खोजें

मान लीजिए कि हमारे पास एन नौकरियों की एक सूची है जहां प्रत्येक नौकरी के तीन पैरामीटर हैं। 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

  • अगर जॉब्स[मिड]।फिनिश <=जॉब्स[इंडेक्स]।स्टार्ट, फिर -

    • अगर नौकरियां [मध्य + 1]। समाप्त <=नौकरियां [सूचकांक]। प्रारंभ करें, फिर -

      • बायां :=मध्य + 1

    • बीच में लौटें

      • बीच में लौटें

  • अन्यथा

    • दाएं:=मध्य - 1

• वापसी -1

• मुख्य विधि से, निम्न कार्य करें -

• समाप्ति समय के आधार पर सरणी जॉब_लिस्ट को सॉर्ट करें

• नौकरियों के लिए एक टेबल बनाएं जिसे टेबल ऑफ साइज n कहा जाता है

• तालिका [0]। मूल्य:=job_list [0]। लाभ

• तालिका के अंत में job_list[0] डालें[0]

• इनिशियलाइज़ करने के लिए मैं :=1, जब i

  • शामिल_लाभ :=job_list[i]. लाभ

  • l :=find_no_conflict(job_list, i)

  • यदि l, -1 के बराबर नहीं है, तो −

    • शामिल_लाभ :=शामिल_लाभ + तालिका [एल]। मूल्य

  • अगर शामिल_लाभ> तालिका[i - 1]। मान, तो −

    • तालिका [i]। मूल्य:=शामिल_लाभ

    • तालिका [i]। नौकरी:=तालिका [एल]। नौकरी

    • तालिका के अंत में job_list[i] डालें[i]

  • अन्यथा

    • तालिका [i]:=तालिका [i - 1]

• तालिका से कार्य प्रदर्शित करें

• इष्टतम लाभ प्रदर्शित करें:=तालिका [n - 1]। मान

उदाहरण (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