Найдите вакансии, участвующие в взвешенном планировании работ
Дано N работ, каждая из которых представлена следующими тремя элементами.
1. Время начала
2. Время окончания
3. Связанная прибыль или стоимость
Найдите подмножество работ, связанных с максимальной прибылью, такое, что никакие две работы в подмножестве не перекрываются.
Примеры:
Вход: Количество рабочих мест n = 4 Сведения о вакансии {время начала, время окончания, прибыль} Иов 1: {1, 2, 50} Иов 2: {3, 5, 20} Иов 3: {6, 19, 100} Иов 4: {2, 100, 200} Выход: Рабочие места, приносящие максимальную прибыль: Иов 1: {1, 2, 50} Иов 4: {2, 100, 200}
В предыдущем посте мы обсуждали проблему взвешенного планирования заданий. Тем не менее, пост касался только кода, связанного с нахождением максимальной прибыли. В этом посте мы также напечатаем задания, приносящие максимальную прибыль.
Пусть arr [0..n-1] будет входным массивом Jobs. Мы определяем массив DP [] так, что DP [i] хранит задействованные задания для достижения максимальной прибыли массива arr [0..i]. т.е. DP [i] хранит решение подзадачи arr [0..i]. Остальной алгоритм остается таким же, как обсуждалось в предыдущем посте.
Below is its C++ implementation –
// C++ program for weighted job scheduling using Dynamic // Programming and Binary Search #include <bits/stdc++.h> using namespace std; // A job has start time, finish time and profit. struct Job { int start, finish, profit; }; // to store subset of jobs struct weightedJob { // vector of Jobs vector<Job> job; // find profit associated with included Jobs int value; }; // A utility function that is used for sorting events // according to finish time bool jobComparator(Job s1, Job s2) { return (s1.finish < s2.finish); } // A Binary Search based function to find the latest job // (before current job) that doesn"t conflict with current // job. "index" is index of the current job. This function // returns -1 if all jobs before index conflict with it. The // array jobs[] is sorted in increasing order of finish time int latestNonConflict(Job jobs[], int index) { // Initialize "lo" and "hi" for Binary Search int lo = 0, hi = index - 1; // Perform binary Search iteratively while (lo <= hi) { int mid = (lo + hi) / 2; if (jobs[mid].finish <= jobs[index].start) { if (jobs[mid + 1].finish <= jobs[index].start) lo = mid + 1; else return mid; } else hi = mid - 1; } return -1; } // The main function that finds the subset of jobs // associated with maximum profit such that no two // jobs in the subset overlap. int findMaxProfit(Job arr[], int n) { // Sort jobs according to finish time sort(arr, arr + n, jobComparator); // Create an array to store solutions of subproblems. // DP[i] stores the Jobs involved and their total profit // till arr[i] (including arr[i]) weightedJob DP[n]; // initialize DP[0] to arr[0] DP[0].value = arr[0].profit; DP[0].job.push_back(arr[0]); // Fill entries in DP[] using recursive property for ( int i = 1; i < n; i++) { // Find profit including the current job int inclProf = arr[i].profit; int l = latestNonConflict(arr, i); if (l != - 1) inclProf += DP[l].value; // Store maximum of including and excluding if (inclProf > DP[i - 1].value) { DP[i].value = inclProf; // including previous jobs and current job DP[i].job = DP[l].job; DP[i].job.push_back(arr[i]); } else // excluding the current job DP[i] = DP[i - 1]; } // DP[n - 1] stores the result cout << "Optimal Jobs for maximum profits are
" ; for ( int i=0; i<DP[n-1].job.size(); i++) { Job j = DP[n-1].job[i]; cout << "(" << j.start << ", " << j.finish << ", " << j.profit << ")" << endl; } cout << "
Total Optimal profit is " << DP[n - 1].value; } // Driver program int main() { Job arr[] = {{3, 5, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200} }; int n = sizeof (arr)/ sizeof (arr[0]); findMaxProfit(arr, n); return 0; } |
Выход:
Оптимальные рабочие места для максимальной прибыли - это (1, 2, 50) (2, 100, 200) Итого Оптимальная прибыль 250
Эта статья предоставлена Адитьей Гоэлем . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.