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

Жадность — это алгоритмическая парадигма, которая создает решение по частям, всегда выбирая следующую часть, которая предлагает наиболее очевидную и немедленную выгоду. Жадные алгоритмы используются для задач оптимизации. Задача оптимизации может быть решена с помощью Greedy, если задача обладает
следующим свойством: На каждом шаге мы можем сделать выбор, который выглядит наилучшим в данный момент, и мы получим оптимальное решение полной
задачи. .

Рассмотрим следующие 6 действий.
start[] = {1, 3, 0, 5, 8, 5};
finish[] = {2, 4, 6, 7, 9, 9};
Максимальный набор действий, которые могут быть выполнены
одним человеком, составляет {0, 1, 3, 4}.

Здесь,

я=0 — — — старт[я]=1

j=1, старт[j] › финиш[i], 3›2, i=1

j=2, 0>4 возвращает ложь

j=3, 5>4, возвращает true, i=3

j=4, 8›7, возвращает true, i=4

j=5, 5›9 возвращает ложь.

Выход: 0, 1, 3, 4

Код:

#include<stdio.h>
void activitySelection(int s[], int f[], int n) {
 int i=0, j;
 printf(“%d “,i);
 for(j=1;j<n;j++) {
  if(s[j]>f[i]) {
  printf(“%d “,j);
  i=j;
  }
 }
}
int main() {
 int s[]={1,3,0,5,8,5},f[]={2,4,6,7,9,9}, n;
 n=sizeof(s)/sizeof(s[0]);
 activitySelection(s,f,n);
 return 0;
}