So verwenden Sie den Aktivitätsauswahlalgorithmus in C++

So verwenden Sie den Aktivitätsauswahlalgorithmus in C++

Der Aktivitätsauswahlalgorithmus (Activity Selection Algorithm) ist ein klassischer Greedy-Algorithmus, der zur Lösung von Aktivitätsplanungsproblemen verwendet wird. Bei einer Reihe von Start- und Endzeiten für Aktivitäten besteht das Ziel des Algorithmus darin, die größte Menge kompatibler Aktivitäten auszuwählen, d. h. die maximale Anzahl von Aktivitäten, die nicht miteinander in Konflikt stehen und gleichzeitig ausgeführt werden können. In diesem Artikel wird erläutert, wie Sie mit C++ den Aktivitätsauswahlalgorithmus implementieren, und es werden spezifische Codebeispiele angehängt.

Algorithmusidee:

Die Grundidee des Aktivitätsauswahlalgorithmus besteht darin, die Aktivitäten zunächst nach ihrer Endzeit zu sortieren. Wählen Sie dann die Aktivität mit der frühesten Endzeit aus und schließen Sie andere Aktivitäten aus, die damit in Konflikt stehen. Die spezifischen Schritte sind wie folgt:

1. Zuerst müssen Sie eine Struktur definieren, um jede Aktivität darzustellen. Die Struktur enthält die Startzeit und Endzeit der Aktivität.

struct Activity
{
    int start;
    int end;
};

2. Dann definieren Sie eine Funktion, um den Aktivitätsauswahlalgorithmus zu implementieren. Die Eingabe der Funktion ist ein Array von Aktivitäten und die Größe des Arrays, und die Ausgabe ist ein maximal konsistenter Satz von Aktivitäten.

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. Erstellen Sie abschließend ein Aktivitätsarray in der Hauptfunktion und rufen Sie die Aktivitätsauswahlfunktion auf, um den maximal konsistenten Aktivitätssatz auszudrucken.

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

Codebeispielanalyse:

Legen Sie zunächst in der definierten Struktur die Startzeit (Start) und die Endzeit (Ende) jeder Aktivität als Mitglieder der Struktur fest.

Sortieren Sie dann in der implementierten Aktivitätsauswahlfunktion zunächst das Aktivitätsarray nach der Endzeit der Aktivität, sodass die nachfolgenden Aktivitäten bequem in der Reihenfolge der Endzeit ausgewählt werden können.

Als nächstes definieren Sie einen Vektorcontainer selectedActivities, um den größten konsistenten Satz von Aktivitäten zu speichern und ihm die erste Aktivität hinzuzufügen.

Dann beginnen Sie mit der zweiten Aktivität und wiederholen Sie die restlichen Aktivitäten. Wenn die Startzeit der aktuellen Aktivität größer oder gleich der Endzeit der zuletzt ausgewählten Aktivität ist, wird die Aktivität zum maximal kompatiblen Aktivitätssatz hinzugefügt und als letzte aktuell ausgewählte Aktivität festgelegt.

Erstellen Sie abschließend ein Aktivitätsarray in der Hauptfunktion, rufen Sie die Aktivitätsauswahlfunktion auf und drucken Sie den maximal konsistenten Aktivitätssatz aus.

Zusammenfassung:

Anhand des obigen Beispielcodes können wir sehen, wie der Aktivitätsauswahlalgorithmus in C++ implementiert wird. Eine Greedy-Strategie wird verwendet, um die größte Menge kompatibler Aktivitäten basierend auf ihren Endzeiten auszuwählen. Algorithmen zur Aktivitätsauswahl werden im wirklichen Leben häufig verwendet, z. B. bei der Vereinbarung von Besprechungen, im Projektmanagement usw.

【Referenzen】

[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L. & Stein, C. (2009). MIT Press.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den Aktivitätsauswahlalgorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!