Рубрики

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

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

  1. Начальное время
  2. Время окончания
  3. Прибыль или стоимость, связанная

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

Пример:

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".

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

Алгоритм является:

  1. Сортировка заданий по неубывающим временам окончания.
  2. Для каждого i от 1 до n определите максимальное значение расписания из подпоследовательности заданий [0..i]. Сделайте это, сравнив включение задания [i] с расписанием с исключением задания [i] с расписанием, а затем взяв макс.

Найти прибыль с включением работы [я]. нам нужно найти самую последнюю работу, которая не противоречит работе [i]. Идея состоит в том, чтобы использовать бинарный поиск, чтобы найти последнюю не конфликтующую работу.

C / C ++

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

using namespace std;

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

struct Job

{

    int start, finish, profit;

};

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

bool myfunction(Job s1, Job s2)

{

    return (s1.finish < s2.finish);

}

  
// Функция бинарного поиска для поиска последней работы
// (до текущей работы), которая не конфликтует с текущей
// работа. «index» - это индекс текущей работы. Эта функция
// возвращает -1, если все задания до индекса конфликтуют с ним.
// Массив jobs [] сортируется в порядке возрастания финиша
// время

int binarySearch(Job jobs[], int index)

{

    // Инициализируем lo и hi для бинарного поиска

    int lo = 0, hi = index - 1;

  

    // Выполняем бинарный поиск итеративно

    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;

}

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

int findMaxProfit(Job arr[], int n)

{

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

    sort(arr, arr+n, myfunction);

  

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

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

    int *table = new int[n];

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

  

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

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

    {

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

        int inclProf = arr[i].profit;

        int l = binarySearch(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 << "Optimal profit is " << findMaxProfit(arr, n);

    return 0;

}

питон

# Программа Python для взвешенного планирования заданий с использованием Dynamic
# Программирование и бинарный поиск

  
# Класс для представления работы

class Job:

    def __init__(self, start, finish, profit):

        self.start  = start

        self.finish = finish

        self.profit  = profit

  

  
# Функция бинарного поиска для поиска последней работы
# (до текущей работы), которая не конфликтует с текущей
# работа. «index» - это индекс текущей работы. Эта функция
# возвращает -1, если все задания до индекса конфликтуют с ним.
# Массив заданий [] сортируется в порядке возрастания финиша
# время

def binarySearch(job, start_index):

  

    # Инициализировать 'lo' и 'hi' для бинарного поиска

    lo = 0

    hi = start_index - 1

  

    # Выполнять бинарный поиск итеративно

    while lo <= hi:

        mid = (lo + hi) // 2

        if job[mid].finish <= job[start_index].start:

            if job[mid + 1].finish <= job[start_index].start:

                lo = mid + 1

            else:

                return mid

        else:

            hi = mid - 1

    return -1

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

def schedule(job):

    

    # Сортировка работ по времени окончания

    job = sorted(job, key = lambda j: j.finish)

  

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

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

    n = len(job) 

    table = [0 for _ in range(n)]

  

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

  

    # Заполнить записи в таблице [], используя рекурсивное свойство

    for i in range(1, n):

  

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

        inclProf = job[i].profit

        l = binarySearch(job, i)

        if (l != -1):

            inclProf += table[l];

  

        # Хранить максимум включающий и исключающий

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

  

    return table[n-1]

  
# Код драйвера для проверки вышеуказанной функции

job = [Job(1, 2, 50), Job(3, 5, 20), 

      Job(6, 19, 100), Job(2, 100, 200)]

print("Optimal profit is"),

print schedule(job)

Джава

// Java-программа для взвешенного планирования заданий в O (nLogn)
// время

import java.util.Arrays;

import java.util.Comparator;

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

class Job

{

    int start, finish, profit;

  

    // Конструктор

    Job(int start, int finish, int profit)

    {

        this.start = start;

        this.finish = finish;

        this.profit = profit;

    }

}

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

class JobComparator implements Comparator<Job>

{

    public int compare(Job a, Job b)

    {

        return a.finish < b.finish ? -1 : a.finish == b.finish ? 0 : 1;

    }

}

  

public class WeightedIntervalScheduling

{

    / * Бинарный поиск на основе функции, чтобы найти последнюю работу

      (до текущей работы), которая не конфликтует с текущей

      работа. «index» - это индекс текущей работы. Эта функция

      возвращает -1, если все задания до индекса конфликтуют с ним.

      Массив заданий [] сортируется в порядке возрастания финиша

      время. * /

    static public int binarySearch(Job jobs[], int index)

    {

        // Инициализируем lo и hi для бинарного поиска

        int lo = 0, hi = index - 1;

  

        // Выполняем бинарный поиск итеративно

        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;

    }

  

    // Основная функция, которая возвращает максимально возможное

    // прибыль от заданного массива рабочих мест

    static public int schedule(Job jobs[])

    {

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

        Arrays.sort(jobs, new JobComparator());

  

        // Создать массив для хранения решений подзадач.

        // таблица [i] сохраняет прибыль за рабочие места до рабочих мест [i]

        // (включая вакансии [i])

        int n = jobs.length;

        int table[] = new int[n];

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

  

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

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

        {

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

            int inclProf = jobs[i].profit;

            int l = binarySearch(jobs, i);

            if (l != -1)

                inclProf += table[l];

  

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

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

        }

  

        return table[n-1];

    }

  

    // Метод драйвера для тестирования выше

    public static void main(String[] args)

    {

        Job jobs[] = {new Job(1, 2, 50), new Job(3, 5, 20),

                      new Job(6, 19, 100), new Job(2, 100, 200)};

  

        System.out.println("Optimal profit is " + schedule(jobs));

    }

}


Выход:

Optimal profit is 250

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

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

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

0.00 (0%) 0 votes