Рубрики

Java-программа для задачи выбора действий | Жадный Алго-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[] ]

Джава

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

import java.util.*;

import java.lang.*;

import java.io.*;

  

class ActivitySelection {

    // Печатает максимальный набор действий, которые могут быть выполнены одним

    // человек, по одному за раз.

    // n -> Общее количество действий

    // s [] -> Массив, содержащий время начала всех действий

    // f [] -> Массив, содержащий время окончания всех действий

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

    {

        int i, j;

  

        System.out.print("Following activities are selected : n");

  

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

        i = 0;

        System.out.print(i + " ");

  

        // Рассмотрим остальные мероприятия

        for (j = 1; j < n; j++) {

            // Если время начала действия больше или

            // равно времени окончания ранее выбранного

            // активность, затем выберите ее

            if (s[j] >= f[i]) {

                System.out.print(j + " ");

                i = j;

            }

        }

    }

  

    // программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args)

    {

        int s[] = { 1, 3, 0, 5, 8, 5 };

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

        int n = s.length;

  

        printMaxActivities(s, f, n);

    }

}

Выход:

Following activities are selected : n0 1 3 4

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

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

Java-программа для задачи выбора действий | Жадный Алго-1

0.00 (0%) 0 votes