Cara menggunakan algoritma pemilihan aktiviti dalam C++

Cara menggunakan algoritma pemilihan aktiviti dalam C++

Algoritma pemilihan aktiviti (Algoritma Pemilihan Aktiviti) ialah algoritma tamak klasik untuk acara Selesaikan isu penjadualan. Memandangkan satu set masa mula dan tamat untuk aktiviti, matlamat algoritma adalah untuk memilih set terbesar aktiviti serasi, iaitu, bilangan maksimum aktiviti yang tidak bercanggah antara satu sama lain dan boleh dilakukan secara serentak. Artikel ini akan memperkenalkan cara menggunakan C++ untuk melaksanakan algoritma pemilihan aktiviti dan melampirkan contoh kod tertentu.

Idea algoritma:

Idea asas algoritma pemilihan aktiviti ialah menyusun dahulu aktiviti mengikut masa tamatnya. Kemudian pilih aktiviti dengan masa tamat yang paling awal, tidak termasuk aktiviti lain yang bercanggah dengannya. Langkah-langkah khusus adalah seperti berikut:

1. Pertama, anda perlu menentukan struktur untuk mewakili setiap aktiviti. Struktur mengandungi masa mula dan masa tamat aktiviti.

struct Activity
{
    int start;
    int end;
};

2. Kemudian, tentukan fungsi untuk melaksanakan algoritma pemilihan aktiviti. Input fungsi ialah tatasusunan aktiviti dan saiz tatasusunan, dan output ialah set aktiviti maksimum yang konsisten.

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. Akhir sekali, bina tatasusunan aktiviti dalam fungsi utama dan panggil fungsi pemilihan aktiviti untuk mencetak set aktiviti konsisten maksimum.

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

Analisis sampel kod:

Pertama, dalam struktur yang ditentukan, tetapkan masa mula (mula) dan masa tamat (tamat) setiap aktiviti ) sebagai ahli struktur.

Kemudian, dalam fungsi pemilihan aktiviti yang dilaksanakan, tatasusunan aktiviti terlebih dahulu diisih mengikut masa tamat aktiviti, supaya apabila aktiviti seterusnya dipilih, susunan masa tamat boleh diikuti dengan mudah .

Seterusnya, tentukan bekas vektor yang dipilihAktiviti untuk menyimpan set terbesar aktiviti serasi dan menambah aktiviti pertama padanya.

Kemudian, mulakan dari aktiviti kedua dan rentas aktiviti yang tinggal. Jika masa mula aktiviti semasa adalah lebih besar daripada atau sama dengan masa tamat aktiviti terakhir yang dipilih, aktiviti itu ditambahkan pada set aktiviti serasi maksimum dan ditetapkan sebagai aktiviti terakhir yang dipilih pada masa ini.

Akhir sekali, buat tatasusunan aktiviti dalam fungsi utama, panggil fungsi pemilihan aktiviti dan cetak set aktiviti konsisten maksimum.

Ringkasan:

Melalui contoh kod di atas, kita dapat melihat cara melaksanakan algoritma pemilihan aktiviti dalam C++. Strategi tamak digunakan untuk memilih set terbesar aktiviti serasi berdasarkan masa tamatnya. Algoritma pemilihan aktiviti digunakan secara meluas dalam kehidupan sebenar, seperti pengaturan mesyuarat, pengurusan projek, dsb.

【Rujukan】

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

Atas ialah kandungan terperinci Cara menggunakan algoritma pemilihan aktiviti dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!