1) Жадный алгоритм

Что такое жадный алгоритм?

В GREEDY ALGORITHM набор ресурсов рекурсивно разделяется на основе максимальной, немедленной доступности этого ресурса на любом этапе выполнения.

Чтобы решить проблему, основанную на жадном подходе, есть два этапа

1. сканирование списка предметов
2. оптимизация.

Эти этапы выполняются параллельно по ходу деления массива.

Архитектура Жадного подхода

Код Объяснение

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_ACTIVITIES 12

Объяснение кода:

1. Включенные заголовочные файлы / классы
2. Максимальное количество действий, предоставляемых пользователем.

using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

Объяснение кода:

1. Пространство имен для потоковых операций.
2. Определение класса для ВРЕМЕНИ
3. Часовая метка.
4. ВРЕМЯ конструктор по умолчанию
5. Переменная часов.

class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

    public: Activity()
    {
   	 start = finish = TIME();
    }
};

Объяснение кода:

1. Определение класса из деятельности
2. Отметки времени, определяющие продолжительность
3. Все метки времени инициализируются в 0 в конструкторе по умолчанию

class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

Объяснение кода:

1. Часть 1 определения класса планировщика.
2. Рассматриваемый индекс является отправной точкой для сканирования массива.
3. Индекс инициализации используется для назначения случайных меток времени.
4. Массив объектов деятельности динамически размещается с помощью оператора new.
5. Запланированный указатель определяет текущее базовое местоположение для жадности.

Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Объяснение кода:

1. Конструктор планировщика — часть 2 определения класса планировщика.
2. Рассматриваемый индекс определяет текущее начало текущего сканирования.
3. Текущий жадный экстент не определен в начале.

for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++)
 {
   		 current_activities[init_index].start.hours =
   			 rand() % 12;

   		 current_activities[init_index].finish.hours =
   			 current_activities[init_index].start.hours +
   				 (rand() % 2);

   		 printf("\nSTART:%d END %d\n",
   		 current_activities[init_index].start.hours
   		 ,current_activities[init_index].finish.hours);
 }
…
…

Объяснение кода:

1. Цикл for для инициализации начальных и конечных часов каждого из запланированных на данный момент действий.
2. Начальная инициализация времени.
3. Инициализация времени окончания всегда после или точно в начальный час.
4. Оператор отладки для распечатки выделенных длительностей.

	public:
   		 Activity * activity_select(int);
};

Объяснение кода:

1. Часть 4 — последняя часть определения класса планировщика.
2. Функция выбора активности берет индекс начальной точки в качестве основы и делит жадный квест на жадные подзадачи.

Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
… 

1. Используя оператор разрешения области (: :), предоставляется определение функции.
2. Рассматриваемый индекс — это индекс, называемый по значению. Greedy_extent — это инициализированный индекс после рассматриваемого индекса.

Activity * Scheduler :: activity_select(int considered_index)
{
    	while( (greedy_extent < MAX_ACTIVITIES ) &&
   	 ((this->current_activities[greedy_extent]).start.hours <
   		 (this->current_activities[considered_index]).finish.hours ))
    	{
   	 printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",
   	 (this->current_activities[greedy_extent]).start.hours,
   	 (this->current_activities[greedy_extent]).finish.hours,
   	 greedy_extent + 1);
   	 greedy_extent++;
    	}
…
...

Объяснение кода:

1. Основная логика — жадная степень ограничена количеством действий.
2. Время начала текущей деятельности проверяется как планируемое до того, как завершится рассматриваемая деятельность (заданная с помощью рассматриваемого индекса).
3. Пока это возможно, печатается дополнительный оператор отладки.
4. Переход к следующему индексу в массиве активности

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5 
finish6
 activity:3

Schedule start:9 
finish10
 activity:5