Comment utiliser l'algorithme de sélection d'activité en C++

Comment utiliser l'algorithme de sélection d'activité en C++

L'algorithme de sélection d'activité (Activity Selection Algorithm) est un algorithme glouton classique utilisé pour résoudre des problèmes de planification d'activités. Étant donné un ensemble d’heures de début et de fin pour les activités, le but de l’algorithme est de sélectionner le plus grand ensemble d’activités compatibles, c’est-à-dire le nombre maximum d’activités qui n’entrent pas en conflit les unes avec les autres et peuvent être exécutées simultanément. Cet article expliquera comment utiliser C++ pour implémenter l'algorithme de sélection d'activité et joindra des exemples de code spécifiques.

Idée d'algorithme :

L'idée de base de l'algorithme de sélection d'activité est de trier d'abord les activités en fonction de leur heure de fin. Sélectionnez ensuite l'activité dont l'heure de fin est la plus proche, en excluant les autres activités en conflit avec elle. Les étapes spécifiques sont les suivantes :

1. Tout d'abord, vous devez définir une structure pour représenter chaque activité. La structure contient l'heure de début et l'heure de fin de l'activité.

struct Activity
{
    int start;
    int end;
};

2. Ensuite, définissez une fonction pour implémenter l'algorithme de sélection d'activité. L'entrée de la fonction est un tableau d'activités et la taille du tableau, et la sortie est un ensemble d'activités cohérent maximum.

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. Enfin, construisez un tableau d'activités dans la fonction principale et appelez la fonction de sélection d'activité pour imprimer l'ensemble d'activités cohérent maximum.

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

Analyse d'un exemple de code :

Tout d'abord, dans la structure définie, définissez l'heure de début (start) et l'heure de fin (end) de chaque activité en tant que membres de la structure.

Ensuite, dans la fonction de sélection d'activité implémentée, triez d'abord le tableau d'activités en fonction de l'heure de fin de l'activité, afin que les activités suivantes puissent être sélectionnées facilement dans l'ordre de l'heure de fin.

Ensuite, définissez un conteneur vectoriel selectedActivities pour enregistrer le plus grand ensemble cohérent d'activités et y ajouter la première activité.

Ensuite, commencez par la deuxième activité et répétez les activités restantes. Si l'heure de début de l'activité en cours est supérieure ou égale à l'heure de fin de la dernière activité sélectionnée, l'activité est ajoutée à l'ensemble d'activités maximum compatible et définie comme la dernière activité actuellement sélectionnée.

Enfin, créez un tableau d'activités dans la fonction principale, appelez la fonction de sélection d'activité et imprimez l'ensemble d'activités cohérent maximum.

Résumé :

Grâce à l'exemple de code ci-dessus, nous pouvons voir comment implémenter l'algorithme de sélection d'activité en C++. Une stratégie gloutonne est utilisée pour sélectionner le plus grand ensemble d’activités compatibles en fonction de leurs heures de fin. Les algorithmes de sélection d'activités sont largement utilisés dans la vie réelle, comme l'organisation de réunions, la gestion de projet, etc.

【Références】

[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C. (2009). Introduction aux algorithmes (3e édition).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!