Рубрики

Проблема последовательности заданий

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

Примеры:

Input: Four Jobs with following 
deadlines and profits
JobID  Deadline  Profit
  a      4        20   
  b      1        10
  c      1        40  
  d      1        30
Output: Following is maximum 
profit sequence of jobs
        c, a   


Input:  Five Jobs with following
deadlines and profits
JobID   Deadline  Profit
  a       2        100
  b       1        19
  c       2        27
  d       1        25
  e       3        15
Output: Following is maximum 
profit sequence of jobs
        c, a, e

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

Это стандартная проблема алгоритма жадности. Ниже приводится алгоритм.

1) Sort all jobs in decreasing order of profit.
2) Initialize the result sequence as first job in sorted jobs.
3) Do following for remaining n-1 jobs
…….a) If the current job can fit in the current result sequence without missing the deadline, add current job to the result. Else ignore the current job.

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

C ++

// Программа для поиска максимальной последовательности заданий из данного массива
// работ со сроками и прибылью
#include<iostream>
#include<algorithm>

using namespace std;

  
// Структура для представления работы

struct Job

{

   char id;      // Идентификатор работы

   int dead;    // Крайний срок работы

   int profit;  // Прибыль, если работа закончена раньше или в срок

};

  
// Эта функция используется для сортировки всех заданий по прибыли

bool comparison(Job a, Job b)

{

     return (a.profit > b.profit);

}

  
// Возвращает минимальное количество требуемых платформ

void printJobScheduling(Job arr[], int n)

{

    // Сортировка всех заданий в порядке убывания prfit

    sort(arr, arr+n, comparison);

  

    int result[n]; // Сохранить результат (последовательность заданий)

    bool slot[n];  // Отслеживать свободные временные интервалы

  

    // Инициализируем все слоты, чтобы быть свободными

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

        slot[i] = false;

  

    // Перебирать все заданные задания

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

    {

       // Найти свободный слот для этой работы (обратите внимание, что мы начинаем

       // из последнего возможного слота)

       for (int j=min(n, arr[i].dead)-1; j>=0; j--)

       {

          // Найден свободный слот

          if (slot[j]==false)

          {

             result[j] = i;  // Добавить эту работу в результат

             slot[j] = true; // Занять этот слот

             break;

          }

       }

    }

  

    // Распечатать результат

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

       if (slot[i])

         cout << arr[result[i]].id << " ";

}

  
// Программа драйвера для тестирования методов

int main()

{

    Job arr[] = { {'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27},

                   {'d', 1, 25}, {'e', 3, 15}};

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

    cout << "Following is maximum profit sequence of jobsn";

    printJobScheduling(arr, n);

    return 0;

}

python3

# Программа для поиска максимальной прибыли
# последовательность заданий из данного массива
# рабочих мест с указанием сроков и прибыли

  
# функция для планирования работы займет 2
# массив аргументов и нет заданий для планирования

def printJobScheduling(arr, t):

  

    # длина массива

    n = len(arr)

  

    # Сортировка всех заданий по

    # уменьшение порядка прибыли

    for i in range(n):

        for j in range(n - 1 - i):

            if arr[j][2] < arr[j + 1][2]:

                arr[j], arr[j + 1] = arr[j + 1], arr[j]

  

    # Чтобы отслеживать свободные временные интервалы

    result = [False] * t

  

    # Сохранить результат (последовательность заданий)

    job = ['-1'] * t

  

    # Перебирать все заданные задания

    for i in range(len(arr)):

  

        # Найти свободный слот для этой работы

        # (Обратите внимание, что мы начинаем с

        # последний возможный слот)

        for j in range(min(t - 1, arr[i][1] - 1), -1, -1):

              

            # Найден свободный слот

            if result[j] is False:

                result[j] = True

                job[j] = arr[i][0]

                break

  

    # распечатать последовательность

    print(job)

  
# Код водителя

arr = [['a', 2, 100], # Job Array

       ['b', 1, 19],

       ['c', 2, 27],

       ['d', 1, 25],

       ['e', 3, 15]]

  

  

print("Following is maximum profit sequence of jobs")

printJobScheduling(arr, 3) # Вызов функции

  
# Этот код добавлен
# Анубхав Радж Сингх


Выход:

Following is maximum profit sequence of jobs
c a e

Временная сложность вышеуказанного решения составляет O (n 2 ). Его можно оптимизировать с помощью структуры данных Disjoint Set. Пожалуйста, смотрите ниже пост для деталей.

Проблема последовательности работы | Набор 2 (Использование несвязанного набора)

Источники:
http://ocw.mit.edu/courses/civil-and-environmental-engineering/1-204-computer-algorithms-in-systems-engineering-spring-2010/lecture-notes/MIT1_204S10_lec10.pdf

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

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

Проблема последовательности заданий

0.00 (0%) 0 votes