Greedy-Algorithmus und seine Implementierung in C++

Der Greedy-Algorithmus ist eine häufig verwendete Algorithmusidee und wird häufig bei vielen Problemen eingesetzt. Der Kerngedanke besteht darin, bei der Entscheidungsfindung in jedem Schritt nur die unmittelbar optimale Lösung zu berücksichtigen, ohne die langfristigen Auswirkungen zu berücksichtigen.

In C++ umfasst die Implementierung gieriger Algorithmen häufig grundlegende Operationen wie Sortieren und Datenverarbeitung. Im Folgenden stellen wir die Idee des Greedy-Algorithmus und seine Implementierung in C++ für mehrere typische Probleme vor.

1. Aktivitätsplanungsproblem

Bei einer Reihe von Aktivitäten hat jede Aktivität ihre Startzeit und Endzeit, und eine Person kann jeweils nur an einer Aktivität teilnehmen. Fragen Sie, wie Sie Aktivitäten organisieren, um sicherzustellen, dass diese Person an der größtmöglichen Anzahl an Aktivitäten teilnimmt.

Die Idee des Greedy-Algorithmus besteht darin, zunächst jede Aktivität in aufsteigender Reihenfolge nach der Endzeit zu sortieren und dann ausgehend von der ersten Aktivität die Aktivität mit der frühesten Endzeit als erste Aktivität auszuwählen, an der teilgenommen werden soll. Wählen Sie dann aus den verbleibenden Aktivitäten die Aktivität mit der frühesten Endzeit aus, die mit der aktuellen Aktivität kompatibel ist, und machen Sie sie zur nächsten Aktivität, an der Sie teilnehmen möchten. Wiederholen Sie diesen Vorgang, bis alle Aktivitäten geplant sind.

Das Folgende ist die C++-Code-Implementierung:

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. Huffman-Codierungsproblem

Bei einem gegebenen Satz von Gewichtswerten ist es erforderlich, diese in binäre Zeichenfolgen ungleicher Länge zu codieren, sodass die Codierungslänge der Summe aller Werte entspricht wird minimiert.

Die Idee des Greedy-Algorithmus besteht darin, zunächst die Gewichte in aufsteigender Reihenfolge zu sortieren, in jedem Schritt die beiden Knoten mit den kleinsten Gewichten auszuwählen, um sie zu einem neuen Knoten zu kombinieren, und sein Gewicht als Summe der Gewichte zu definieren der beiden Knoten. Wiederholen Sie diesen Vorgang, bis alle Knoten zu einem Wurzelknoten zusammengefasst sind. Der diesem Wurzelknoten entsprechende Binärbaum ist der Huffman-Baum. Beim Durchlaufen des Huffman-Baums bedeutet das Gehen nach links das Hinzufügen von 0 und das Gehen nach rechts das Hinzufügen von 1, sodass die entsprechende Kodierung jedes Gewichts gelöst werden kann.

Das Folgende ist die C++-Code-Implementierung:

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. Lösen Sie das Münzwechselproblem

Angesichts des Nennwerts eines Münzsatzes und der Menge des Wechselgelds, die vorgenommen werden muss, fragen Sie, wie viele Münzen benötigt werden, um das Problem zu lösen Menge.

Die Idee des Greedy-Algorithmus besteht darin, die Münzen zunächst in absteigender Reihenfolge zu sortieren, dann mit der Münze mit dem größten Nennwert zu beginnen, die Münze so lange zu nehmen, bis keine Auswahl mehr getroffen werden kann, und dann die Münze zu verwenden Münze mit dem nächsthöheren Nennwert, bis der gesamte Betrag eingesammelt ist.

Das Folgende ist die C++-Code-Implementierung:

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

Im tatsächlichen Entwicklungsprozess ist der Greedy-Algorithmus oft nicht die optimale Lösung, aber aufgrund seiner Einfachheit und Effizienz ist er weit verbreitet. Durch die Einführung der oben genannten drei typischen Probleme glaube ich, dass die Leser die Idee des Greedy-Algorithmus und seine Implementierung in C++ besser verstehen und beherrschen können.

Das obige ist der detaillierte Inhalt vonGreedy-Algorithmus und seine Implementierung in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!