Рубрики

C Программа для задачи выбора задач | Жадный Алго-1

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

Example 1 : Consider the following 3 activities sorted by finish time.
     start[]  =  {10, 12, 20};
     finish[] =  {20, 25, 30};
A person can perform at most two activities. The 
maximum set of activities that can be executed 
is {0, 2} [ These are indexes in start[] and 
finish[] ]

Example 2 : Consider the following 6 activities 
sorted by by finish time.
     start[]  =  {1, 3, 0, 5, 8, 5};
     finish[] =  {2, 4, 6, 7, 9, 9};
A person can perform at most four activities. The 
maximum set of activities that can be executed 
is {0, 1, 3, 4} [ These are indexes in start[] and 
finish[] ]

C ++

// C ++ программа для задачи выбора активности.
// Следующая реализация предполагает, что действия
// уже отсортированы по времени окончания
#include <stdio.h>

  
// Печатает максимальный набор действий, которые могут быть выполнены одним
// человек, по одному за раз.
// n -> Общее количество действий
// s [] -> Массив, содержащий время начала всех действий
// f [] -> Массив, содержащий время окончания всех действий

void printMaxActivities(int s[], int f[], int n)

{

    int i, j;

  

    printf("Following activities are selected n");

  

    // Первое действие всегда выбирается

    i = 0;

    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 };

    int f[] = { 2, 4, 6, 7, 9, 9 };

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

    printMaxActivities(s, f, n);

    return 0;

}

Выход:

Following activities are selected n0 1 3 4

Пожалуйста, обратитесь к полной статье о проблеме выбора деятельности | Жадный Алго-1 для более подробной информации!

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

C Программа для задачи выбора задач | Жадный Алго-1

0.00 (0%) 0 votes