如何使用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. 最後，在main函數中建構一個活動數組並呼叫活動選擇函數，列印輸出最大相容活動集合。

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）作為結構體的成員。

然後，在實作的活動選擇函數中，首先根據活動的結束時間對活動數組進行排序，以便後續選擇活動時可以方便地按照結束時間的順序。

接著，定義一個vector容器 selectedActivities 來保存最大相容活動集合，並將第一個活動加入其中。

然後，從第二個活動開始遍歷剩餘的活動。如果目前活動的起始時間大於等於已選取的最後一個活動的結束時間，則將該活動加入最大相容活動集合中，並將該活動設為目前已選取的最後一個活動。

最後，在main函數中建立一個活動數組，呼叫活動選擇函數，並列印輸出最大相容活動集合。

總結：

透過以上的範例程式碼，我們可以看到C 中如何實作活動選擇演算法。透過貪心策略，根據活動的結束時間來選擇最大的相容活動集合。活動選擇演算法在實際生活中有廣泛的應用，例如會議安排、專案管理等。

【參考文獻】

[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd edition). MIT Press .

以上是如何使用C++中的活動選擇演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！