Задача выбора деятельности — это классическая задача оптимизации в информатике. Учитывая набор действий с соответствующим временем начала и окончания, цель состоит в том, чтобы выбрать максимальное количество непересекающихся действий. В этой статье блога мы рассмотрим различные методы решения проблемы выбора действий, включая примеры кода на популярных языках программирования.

1. Жадный алгоритм:
   Жадный алгоритм – это широко используемый подход для эффективного решения задачи выбора действий. Он выбирает действие с самым ранним временем окончания, а затем рекурсивно выбирает действия, которые не пересекаются с ранее выбранными. Вот пример реализации на Python:

def activity_selection(start, finish):
    n = len(finish)
    selected_activities = []
    selected_activities.append(0)
    previous_finish = finish[0]

    for i in range(1, n):
        if start[i] >= previous_finish:
            selected_activities.append(i)
            previous_finish = finish[i]

    return selected_activities

2. Динамическое программирование.
   Динамическое программирование также можно использовать для решения проблемы выбора вида деятельности. Он включает в себя разбиение проблемы на более мелкие подзадачи и сохранение решений, чтобы избежать избыточных вычислений. Вот пример реализации на C++:

#include <iostream>
#include <vector>
#include <algorithm>
int activitySelectionDP(std::vector<int>& start, std::vector<int>& finish) {
    int n = start.size();
    std::vector<int> dp(n, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (finish[j] <= start[i])
                dp[i] = std::max(dp[i], dp[j] + 1);
        }
    }

    return *std::max_element(dp.begin(), dp.end());
}
int main() {
    std::vector<int> start = {1, 3, 0, 5, 8, 5};
    std::vector<int> finish = {2, 4, 6, 7, 9, 9};

    int maxActivities = activitySelectionDP(start, finish);
    std::cout << "Maximum number of activities: " << maxActivities << std::endl;

    return 0;
}

3. Обратное отслеживание.
   Обратное отслеживание — это еще один метод, который можно применить для решения проблемы выбора действия. Он исследует все возможные комбинации активностей и выбирает ту, в которой максимально непересекающиеся активности. Вот пример реализации на Java:

import java.util.ArrayList;
import java.util.List;
public class ActivitySelectionBacktracking {
    public static void main(String[] args) {
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] finish = {2, 4, 6, 7, 9, 9};

        List<Integer> selectedActivities = new ArrayList<>();
        activitySelectionBacktracking(start, finish, selectedActivities, -1);

        System.out.println("Selected activities: " + selectedActivities);
        System.out.println("Maximum number of activities: " + selectedActivities.size());
    }

    private static void activitySelectionBacktracking(int[] start, int[] finish, List<Integer> selectedActivities, int currentActivity) {
        for (int i = currentActivity + 1; i < start.length; i++) {
            if (currentActivity == -1 || start[i] >= finish[currentActivity]) {
                selectedActivities.add(i);
                activitySelectionBacktracking(start, finish, selectedActivities, i);
                selectedActivities.remove(selectedActivities.size() - 1);
            }
        }
    }
}

В этой статье мы рассмотрели различные методы решения проблемы выбора вида деятельности. Мы обсудили жадный алгоритм, динамическое программирование и методы обратного отслеживания, приведя примеры кода на Python, C++ и Java соответственно. Эти методы предлагают различные компромиссы с точки зрения временной сложности и оптимальности решения. В зависимости от конкретных ограничений и требований вашей задачи вы можете выбрать наиболее подходящий подход для эффективного решения проблемы выбора активности.