Рубрики

Взвешенное планирование работы

Дано N рабочих мест, где каждая работа представлена следующими тремя ее элементами.

  1. Начальное время
  2. Время окончания
  3. Прибыль или стоимость (> = 0)

Найдите подмножество заданий с максимальной прибылью, чтобы в подмножестве не перекрывалось ни одно задание.

Пример:

Input: Number of Jobs n = 4
       Job Details {Start Time, Finish Time, Profit}
       Job 1:  {1, 2, 50} 
       Job 2:  {3, 5, 20}
       Job 3:  {6, 19, 100}
       Job 4:  {2, 100, 200}
Output: The maximum profit is 250.
We can get the maximum profit by scheduling jobs 1 and 4.
Note that there is longer schedules possible Jobs 1, 2 and 3 
but the profit with this schedule is 20+50+100 which is less than 250. 

Простая версия этой проблемы обсуждается здесь , где каждая работа имеет одинаковую прибыль или значение. Жадная стратегия выбора видов деятельности здесь не работает, поскольку график с большим количеством рабочих мест может иметь меньшую прибыль или ценность.

Вышеуказанная проблема может быть решена с помощью следующего рекурсивного решения.

1) First sort jobs according to finish time.
2) Now apply following recursive process. 
   // Here arr[] is array of n jobs
   findMaximumProfit(arr[], n)
   {
     a) if (n == 1) return arr[0];
     b) Return the maximum of following two profits.
         (i) Maximum profit by excluding current job, i.e., 
             findMaximumProfit(arr, n-1)
         (ii) Maximum profit by including the current job            
   }

How to find the profit including current job?
The idea is to find the latest job before the current job (in 
sorted array) that doesn't conflict with current job 'arr[n-1]'. 
Once we find such a job, we recur for all jobs till that job and
add profit of current job to result.
In the above example, "job 1" is the latest non-conflicting
for "job 4" and "job 2" is the latest non-conflicting for "job 3".
 

Ниже приведена реализация C ++ вышеуказанного наивного рекурсивного метода.

// C ++ программа для взвешенного планирования заданий с использованием наивного рекурсивного метода
#include <iostream>
#include <algorithm>

using namespace std;

  
// Работа имеет время начала, время окончания и прибыль.

struct Job

{

    int start, finish, profit;

};

  
// служебная функция, используемая для сортировки событий
// согласно времени окончания

bool jobComparataor(Job s1, Job s2)

{

    return (s1.finish < s2.finish);

}

  
// Найти последнюю работу (в отсортированном массиве), которая не
// конфликт с заданием [i]. Если нет совместимой работы,
// тогда он возвращает -1.

int latestNonConflict(Job arr[], int i)

{

    for (int j=i-1; j>=0; j--)

    {

        if (arr[j].finish <= arr[i-1].start)

            return j;

    }

    return -1;

}

  
// Рекурсивная функция, которая возвращает максимально возможное
// прибыль от заданного массива рабочих мест. Массив заданий должен
// сортировать по времени окончания.

int findMaxProfitRec(Job arr[], int n)

{

    // Базовый вариант

    if (n == 1) return arr[n-1].profit;

  

    // Найти прибыль при включении текущей работы

    int inclProf = arr[n-1].profit;

    int i = latestNonConflict(arr, n);

    if (i != -1)

      inclProf += findMaxProfitRec(arr, i+1);

  

    // Найти прибыль, когда текущая работа исключена

    int exclProf = findMaxProfitRec(arr, n-1);

  

    return max(inclProf,  exclProf);

}

  
// Основная функция, которая возвращает максимально возможное
// прибыль от заданного массива рабочих мест

int findMaxProfit(Job arr[], int n)

{

    // Сортировка заданий по времени окончания

    sort(arr, arr+n, jobComparataor);

  

    return findMaxProfitRec(arr, n);

}

  
// Драйвер программы

int main()

{

    Job arr[] = {{3, 10, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200}};

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "The optimal profit is " << findMaxProfit(arr, n);

    return 0;

}

Выход:

The optimal profit is 250

Вышеупомянутое решение может содержать много перекрывающихся подзадач. Например, если lastNonConflicting () всегда возвращает предыдущее задание, findMaxProfitRec (arr, n-1) вызывается дважды, а сложность по времени становится равной O (n * 2 n ). В качестве другого примера, когда lastNonConflicting () возвращает предыдущее задание, есть два рекурсивных вызова для n-2 и n-1. В этом примере рекурсия становится такой же, как числа Фибоначчи.
Таким образом, эта проблема имеет свойства динамического программирования, оптимальной подструктуры и перекрывающихся подзадач .
Как и другие проблемы динамического программирования, мы можем решить эту проблему, создав таблицу, в которой хранится решение подзадач.

Ниже приведена реализация C ++, основанная на динамическом программировании.

// C ++ программа для взвешенного планирования заданий с использованием динамического программирования.
#include <iostream>
#include <algorithm>

using namespace std;

  
// Работа имеет время начала, время окончания и прибыль.

struct Job

{

    int start, finish, profit;

};

  
// служебная функция, используемая для сортировки событий
// согласно времени окончания

bool jobComparataor(Job s1, Job s2)

{

    return (s1.finish < s2.finish);

}

  
// Найти последнюю работу (в отсортированном массиве), которая не
// конфликт с заданием [i]

int latestNonConflict(Job arr[], int i)

{

    for (int j=i-1; j>=0; j--)

    {

        if (arr[j].finish <= arr[i].start)

            return j;

    }

    return -1;

}

  
// Основная функция, которая возвращает максимально возможное
// прибыль от заданного массива рабочих мест

int findMaxProfit(Job arr[], int n)

{

    // Сортировка заданий по времени окончания

    sort(arr, arr+n, jobComparataor);

  

    // Создать массив для хранения решений подзадач. Таблица [I]

    // сохраняет прибыль за работу до arr [i] (включая arr [i])

    int *table = new int[n];

    table[0] = arr[0].profit;

  

    // Заполняем записи в M [] используя рекурсивное свойство

    for (int i=1; i<n; i++)

    {

        // Найти прибыль, включая текущую работу

        int inclProf = arr[i].profit;

        int l = latestNonConflict(arr, i);

        if (l != -1)

            inclProf += table[l];

  

        // Сохраняем максимум включений и исключений

        table[i] = max(inclProf, table[i-1]);

    }

  

    // Сохраняем результат и освобождаем динамическую память для таблицы []

    int result = table[n-1];

    delete[] table;

  

    return result;

}

  
// Драйвер программы

int main()

{

    Job arr[] = {{3, 10, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200}};

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "The optimal profit is " << findMaxProfit(arr, n);

    return 0;

}

Выход:

The optimal profit is 250

Сложность по времени вышеупомянутого решения для динамического программирования составляет O (n 2 ). Обратите внимание, что приведенное выше решение может быть оптимизировано для O (nLogn) с использованием бинарного поиска в latestNonConflict () вместо линейного поиска. Спасибо Garvit за предложение об этой оптимизации. Пожалуйста, смотрите ниже пост для деталей.

Взвешенное планирование заданий за O (n Log n) время

Ссылки:
http://courses.cs.washington.edu/courses/cse521/13wi/slides/06dp-sched.pdf

Эта статья предоставлена Шивам. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Взвешенное планирование работы

0.00 (0%) 0 votes