Взвешенное планирование работ | Набор 2 (с использованием LIS)

Опубликовано: 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}

Пояснение: Максимальную прибыль можно получить, 
планирование заданий 1 и 4 и максимальная прибыль 250.
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

В предыдущем посте мы обсуждали проблему взвешенного планирования заданий. Мы обсудили решение DP, в котором мы в основном включаем или исключаем текущую работу. В этом посте обсуждается еще одно интересное решение DP, в котором мы также печатаем задания. Эта проблема является разновидностью стандартной задачи самой длинной возрастающей подпоследовательности (LIS). Нам нужно небольшое изменение в решении проблемы LIS с помощью динамического программирования.

Сначала нам нужно отсортировать задания по времени начала. Пусть job [0..n-1] будет массивом заданий после сортировки. Мы определяем вектор L так, что L [i] сам является вектором, который хранит взвешенное планирование заданий для задания [0..i], которое заканчивается заданием [i]. Следовательно, для индекса i L [i] может быть рекурсивно записано как -

 L [0] = {работа [0]}
L [i] = {MaxSum (L [j])} + job [i], где j <i и job [j] .finish <= job [i] .start
     = job [i], если такого j нет

Например, рассмотрим пары {3, 10, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200}

After sorting we get, 
{1, 2, 50}, {2, 100, 200}, {3, 10, 20}, {6, 19, 100}

Therefore,
L[0]: {1, 2, 50}
L[1]: {1, 2, 50} {2, 100, 200}
L[2]: {1, 2, 50} {3, 10, 20}
L[3]: {1, 2, 50} {6, 19, 100}

Выбираем вектор с наибольшей прибылью. В данном случае L [1].

Below is the implementation of the above idea – 

C++

// C++ program for weighted job scheduling using LIS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
// A job has start time, finish time and profit.
struct Job
{
    int start, finish, profit;
};
 
// Utility function to calculate sum of all vector
// elements
int findSum(vector<Job> arr)
{
    int sum = 0;
    for (int i = 0; i < arr.size(); i++)
        sum +=  arr[i].profit;
    return sum;
}
 
// comparator function for sort function
int compare(Job x, Job y)
{
    return x.start < y.start;
}
 
// The main function that finds the maximum possible
// profit from given array of jobs
void findMaxProfit(vector<Job> &arr)
{
    // Sort arr[] by start time.
    sort(arr.begin(), arr.end(), compare);
 
    // L[i] stores stores Weighted Job Scheduling of
    // job[0..i] that ends with job[i]
    vector<vector<Job>> L(arr.size());
 
    // L[0] is equal to arr[0]
    L[0].push_back(arr[0]);
 
    // start from index 1
    for (int i = 1; i < arr.size(); i++)
    {
        // for every j less than i
        for (int j = 0; j < i; j++)
        {
            // L[i] = {MaxSum(L[j])} + arr[i] where j < i
            // and arr[j].finish <= arr[i].start
            if ((arr[j].finish <= arr[i].start) &&
                (findSum(L[j]) > findSum(L[i])))
                L[i] = L[j];
        }
        L[i].push_back(arr[i]);
    }
 
    vector<Job> maxChain;
 
    // find one with max profit
    for (int i = 0; i < L.size(); i++)
        if (findSum(L[i]) > findSum(maxChain))
            maxChain = L[i];
 
    for (int i = 0; i < maxChain.size(); i++)
        cout << "(" <<  maxChain[i].start << ", " <<
             maxChain[i].finish << ", "
             <<  maxChain[i].profit << ") ";
}
 
// Driver Function
int main()
{
    Job a[] = { {3, 10, 20}, {1, 2, 50}, {6, 19, 100},
                {2, 100, 200} };
    int n = sizeof(a) / sizeof(a[0]);
 
    vector<Job> arr(a, a + n);
 
    findMaxProfit(arr);
 
    return 0;
}

Java

// Java program for weighted job
// scheduling using LIS
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
 
class Graph{
 
// A job has start time, finish time
// and profit.
static class Job
{
    int start, finish, profit;
 
    public Job(int start, int finish,
               int profit)
    {
        this.start = start;
        this.finish = finish;
        this.profit = profit;
    }
};
 
// Utility function to calculate sum of all
// ArrayList elements
static int findSum(ArrayList<Job> arr)
{
    int sum = 0;
     
    for(int i = 0; i < arr.size(); i++)
        sum += arr.get(i).profit;
         
    return sum;
}
 
// The main function that finds the maximum
// possible profit from given array of jobs
static void findMaxProfit(ArrayList<Job> arr)
{
     
    // Sort arr[] by start time.
    Collections.sort(arr, new Comparator<Job>()
    {
        @Override
        public int compare(Job x, Job y)
        {
            return x.start - y.start;
        }
    });
     
    // sort(arr.begin(), arr.end(), compare);
 
    // L[i] stores stores Weighted Job Scheduling of
    // job[0..i] that ends with job[i]
    ArrayList<ArrayList<Job>> L = new ArrayList<>();
    for(int i = 0; i < arr.size(); i++)
    {
        L.add(new ArrayList<>());
    }
 
    // L[0] is equal to arr[0]
    L.get(0).add(arr.get(0));
 
    // Start from index 1
    for(int i = 1; i < arr.size(); i++)
    {
         
        // For every j less than i
        for(int j = 0; j < i; j++)
        {
             
            // L[i] = {MaxSum(L[j])} + arr[i] where j < i
            // and arr[j].finish <= arr[i].start
            if ((arr.get(j).finish <= arr.get(i).start) &&
                (findSum(L.get(j)) > findSum(L.get(i))))
            {
                ArrayList<Job> copied = new ArrayList<>(
                    L.get(j));
                L.set(i, copied);
            }
        }
        L.get(i).add(arr.get(i));
    }
 
    ArrayList<Job> maxChain = new ArrayList<>();
 
    // Find one with max profit
    for(int i = 0; i < L.size(); i++)
        if (findSum(L.get(i)) > findSum(maxChain))
            maxChain = L.get(i);
 
    for(int i = 0; i < maxChain.size(); i++)
    {
        System.out.printf("(%d, %d, %d) ",
              maxChain.get(i).start,
              maxChain.get(i).finish,
              maxChain.get(i).profit);
    }
}
 
// Driver code
public static void main(String[] args)
{
    Job[] a = { new Job(3, 10, 20),
                new Job(1, 2, 50),
                new Job(6, 19, 100),
                new Job(2, 100, 200) };
 
    ArrayList<Job> arr = new ArrayList<>(
        Arrays.asList(a));
 
    findMaxProfit(arr);
}
}
 
// This code is contributed by sanjeev2552

Выход:

 (1, 2, 50) (2, 100, 200)

Мы можем дополнительно оптимизировать вышеуказанное решение DP, удалив функцию findSum (). Вместо этого мы можем поддерживать другой вектор / массив для хранения суммы максимально возможной прибыли до работы i. Реализацию можно увидеть здесь.

Временная сложность вышеуказанного решения динамического программирования составляет O (n 2 ), где n - количество заданий.
Вспомогательное пространство, используемое программой, равно O (n 2 ).

Эта статья предоставлена Адитьей Гоэлем . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

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