C++에서 활동 선택 알고리즘을 사용하는 방법

C++에서 활동 선택 알고리즘을 사용하는 방법

활동 선택 알고리즘(Activity Selection Algorithm)은 활동 일정 문제를 해결하는 데 사용되는 고전적인 그리디 알고리즘입니다. 활동의 시작 및 종료 시간 세트가 주어지면 알고리즘의 목표는 호환 가능한 활동의 ​​가장 큰 세트, 즉 서로 충돌하지 않고 동시에 수행할 수 있는 최대 활동 수를 선택하는 것입니다. 이 기사에서는 C++를 사용하여 활동 선택 알고리즘을 구현하는 방법을 소개하고 특정 코드 예제를 첨부합니다.

알고리즘 아이디어:

활동 선택 알고리즘의 기본 아이디어는 먼저 종료 시간에 따라 활동을 정렬하는 것입니다. 그런 다음 충돌하는 다른 활동을 제외하고 종료 시간이 가장 빠른 활동을 선택합니다. 구체적인 단계는 다음과 같습니다.

1. 먼저 각 활동을 나타내는 구조를 정의해야 합니다. 구조에는 활동의 시작 시간과 종료 시간이 포함됩니다.

struct Activity
{
    int start;
    int end;
};

2. 그런 다음 활동 선택 알고리즘을 구현하는 함수를 정의합니다. 함수의 입력은 활동의 배열과 배열의 크기이며, 출력은 최대로 일관된 활동 집합입니다.

vector<Activity> activitySelection(Activity arr[], int n)
{
    // 根据结束时间对活动进行排序
    sort(arr, arr + n, [](Activity a, Activity b) {
        return a.end < b.end;
    });

    vector<Activity> selectedActivities;
    selectedActivities.push_back(arr[0]); //选择第一个活动

    int lastSelected = 0;
    //遍历剩余的活动
    for (int i = 1; i < n; i++)
    {
        if (arr[i].start >= arr[lastSelected].end)
        {
            selectedActivities.push_back(arr[i]);
            lastSelected = i;
        }
    }

    return selectedActivities;
}

3. 마지막으로 메인 함수에서 활동 배열을 구성하고 활동 선택 함수를 호출하여 최대 일관된 활동 세트를 인쇄합니다.

int main()
{
    Activity arr[] = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
    int n = sizeof(arr) / sizeof(arr[0]);

    vector<Activity> selectedActivities = activitySelection(arr, n);

    cout << "最大相容活动集合：" << endl;
    for (int i = 0; i < selectedActivities.size(); i++)
    {
        cout << "(" << selectedActivities[i].start << ", " << selectedActivities[i].end << ")" << endl;
    }

    return 0;
}

코드 샘플 분석:

먼저 정의된 구조에서 각 활동의 시작 시간(start)과 종료 시간(end)을 구조의 멤버로 설정합니다.

그 다음 구현된 활동 선택 기능에서는 먼저 활동 종료 시간에 따라 활동 배열을 정렬하여 이후 활동을 종료 시간 순서대로 편리하게 선택할 수 있도록 합니다.

다음으로, 가장 크고 일관된 활동 세트를 저장하고 여기에 첫 번째 활동을 추가하기 위해 벡터 컨테이너 selectedActivities를 정의합니다.

그런 다음 두 번째 활동부터 시작하여 나머지 활동을 반복합니다. 현재 활동의 시작 시간이 마지막으로 선택한 활동의 ​​종료 시간보다 크거나 같은 경우 해당 활동은 최대 호환 가능 활동 세트에 추가되고 현재 마지막으로 선택된 활동으로 설정됩니다.

마지막으로 메인 함수에서 활동 배열을 생성하고 활동 선택 기능을 호출한 후 최대 일관성 활동 세트를 인쇄합니다.

요약:

위의 예제 코드를 통해 C++에서 활동 선택 알고리즘을 구현하는 방법을 확인할 수 있습니다. 탐욕적 전략은 종료 시간을 기준으로 호환 가능한 가장 큰 활동 세트를 선택하는 데 사용됩니다. 활동 선택 알고리즘은 회의 준비, 프로젝트 관리 등 실생활에서 널리 사용됩니다.

【참고자료】

[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009) 알고리즘 소개(3판).

위 내용은 C++에서 활동 선택 알고리즘을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!