Найдите вакансии, участвующие в взвешенном планировании работ

Опубликовано: 20 Января, 2022

Дано 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.

РЕКОМЕНДУЕМЫЕ СТАТЬИ