Algorithme gourmand et son implémentation en C++

L'algorithme glouton est une idée d'algorithme couramment utilisée et est largement utilisé dans de nombreux problèmes. L’idée centrale est de considérer uniquement la solution optimale immédiate lors de la prise de décision à chaque étape, sans tenir compte de l’impact à long terme.

En C++, la mise en œuvre d'algorithmes gloutons implique souvent des opérations de base telles que le tri et le traitement des données. Ci-dessous, nous présenterons l'idée d'un algorithme glouton et son implémentation en C++ pour plusieurs problèmes typiques.

1. Problème de planification des activités

Étant donné un ensemble d'activités, chaque activité a son heure de début et son heure de fin, et une personne ne peut participer qu'à une seule activité à la fois. Demandez comment organiser les activités pour garantir que cette personne participe au nombre maximum d'activités.

L'idée de l'algorithme glouton est de trier d'abord chaque activité par ordre croissant par heure de fin, puis à partir de la première activité, de sélectionner l'activité avec l'heure de fin la plus proche comme première activité à participer. Ensuite, sélectionnez parmi les activités restantes l'activité dont l'heure de fin est la plus proche compatible avec l'activité en cours et faites-en la prochaine activité à laquelle participer. Répétez ce processus jusqu'à ce que toutes les activités aient été planifiées.

Ce qui suit est l'implémentation du code C++ :

struct activity {
    int start;
    int end;
}

bool cmp(activity a, activity b) {
    return a.end < b.end;
}

int arrangeActivities(activity arr[], int n) {
    sort(arr, arr + n, cmp);
    int cnt = 1;
    int lastEnd = arr[0].end;
    for (int i = 1; i < n; i++) {
        if (arr[i].start >= lastEnd) {
            cnt++;
            lastEnd = arr[i].end;
        }
    }
    return cnt;
}

2. Problème de codage de Huffman

Étant donné un ensemble de valeurs de poids, il est nécessaire de les coder en chaînes binaires de longueurs inégales afin que la longueur de codage de la somme de toutes les valeurs est minimisé.

L'idée de​​l'algorithme glouton est de trier d'abord les poids par ordre croissant, de sélectionner les deux nœuds avec les plus petits poids à chaque étape pour les combiner en un nouveau nœud et de définir son poids comme la somme des poids. des deux nœuds. Répétez ce processus jusqu'à ce que tous les nœuds soient combinés en un nœud racine. L'arbre binaire correspondant à ce nœud racine est l'arbre de Huffman. Lors de la traversée de l'arbre de Huffman, marcher vers la gauche signifie ajouter 0, et marcher vers la droite signifie ajouter 1, afin que l'encodage correspondant de chaque poids puisse être résolu.

Voici l'implémentation du code C++ :

struct Node {
    int weight;
    int parent, leftChild, rightChild;
}

bool cmp(Node a, Node b) {
    return a.weight < b.weight;
}

void buildHuffmanTree(Node arr[], int n) {
    // 初始化所有节点
    for (int i = 0; i < n; i++) {
        arr[i].parent = -1;
        arr[i].leftChild = -1;
        arr[i].rightChild = -1;
    }

    // 构建哈夫曼树
    for (int i = n; i < 2 * n - 1; i++) {
        int minIndex1 = -1, minIndex2 = -1;
        for (int j = 0; j < i; j++) {
            if (arr[j].parent == -1) {
                if (minIndex1 == -1) {
                    minIndex1 = j;
                }
                else if (minIndex2 == -1) {
                    minIndex2 = j;
                }
                else {
                    if (arr[j].weight < arr[minIndex1].weight) {
                        minIndex2 = minIndex1;
                        minIndex1 = j;
                    }
                    else if (arr[j].weight < arr[minIndex2].weight) {
                        minIndex2 = j;
                    }
                }
            }
        }
        arr[minIndex1].parent = i;
        arr[minIndex2].parent = i;
        arr[i].leftChild = minIndex1;
        arr[i].rightChild = minIndex2;
        arr[i].weight = arr[minIndex1].weight + arr[minIndex2].weight;
    }
}

void findHuffmanCode(Node arr[], int n) {
    // 从叶节点开始遍历哈夫曼树
    for (int i = 0; i < n; i++) {
        string code = "";
        int currentNode = i;
        while (arr[currentNode].parent != -1) {
            int parent = arr[currentNode].parent;
            if (arr[parent].leftChild == currentNode) {
                code = "0" + code;
            }
            else {
                code = "1" + code;
            }
            currentNode = parent;
        }
        cout << code << endl;
    }
}

3. Résoudre le problème du changement de pièces

Étant donné la valeur nominale d'un ensemble de pièces et le montant de la monnaie à effectuer, demandez combien de pièces sont nécessaires pour constituer l'ensemble de pièces. montant.

L'idée de​​l'algorithme glouton est de trier d'abord les pièces par ordre décroissant, puis de commencer par la pièce ayant la plus grande valeur nominale, de continuer à prendre la pièce jusqu'à ce qu'il ne soit plus possible de faire de choix, puis d'utiliser le pièce de monnaie ayant la valeur nominale la plus élevée jusqu'à ce que la totalité du montant soit collectée.

Voici l'implémentation du code C++ :

bool cmp(int a, int b) {
    return a > b;
}

int minCoinNum(int coins[], int n, int amount) {
    sort(coins, coins + n, cmp);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (amount >= coins[i]) {
            cnt += amount / coins[i];
            amount -= coins[i] * (amount / coins[i]);
        }
    }
    return cnt;
}

Dans le processus de développement actuel, l'algorithme glouton n'est souvent pas la solution optimale, mais sa simplicité et son efficacité le rendent largement utilisé. Grâce à l'introduction des trois problèmes typiques ci-dessus, je pense que les lecteurs peuvent mieux comprendre et maîtriser l'idée de l'algorithme glouton et son implémentation en C++.

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!