C++中的貪心演算法及其實現

貪心演算法是一種常用的演算法思想，在許多問題中都有著廣泛的應用。其核心思想是在做出每一步的決策時，只考慮眼前最優解，而不考慮長遠的影響。

在C 中，貪心演算法的實作經常涉及排序、資料處理等基本操作。下面，我們將針對幾個典型的問題，介紹貪心演算法的思路及其在C 中的實作。

1.活動安排問題

給定一組活動，每個活動有其開始時間和結束時間，同時一個人一次只能參加一個活動。問如何安排活動才能保證這個人參加的活動數量最多。

貪心演算法的想法是先按照每個活動的結束時間升序排序，然後從第一個活動開始，選擇結束時間最早的活動作為第一個參加的活動。接著，從餘下活動中選擇結束時間最早的可與當前活動相容的活動，並將其作為下一個參與的活動。重複此過程，直到所有活動都被安排完為止。

以下是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.哈夫曼編碼問題

給定一組權值，要求將它們編碼為不等長的二進位字符串，使得所有權值相加的編碼長度最小。

貪心演算法的想法是先將權值升序排序，在每一步中選擇權值最小的兩個節點組合成一個新節點，並將其權值定義為這兩個節點的權值之和。重複此過程，直至所有節點都被組合成一個根節點。這個根節點所對應的二元樹即為哈夫曼樹。在遍歷哈夫曼樹時，向左走表示添加0，向右走表示添加1，這樣便可以實現對每個權值對應編碼的求解。

以下是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.求解硬幣找零問題

給定一組硬幣的面值，以及要找零的金額，問最少需要多少個硬幣才能湊出該金額。

貪心演算法的思路是先將硬幣的面值降序排序，然後從面值最大的硬幣開始，不斷取用該硬幣直至無法再選，接著使用面值次大的硬幣，直至湊出所有金額。

以下是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;
}

在實際開發過程中，貪心演算法往往不是最優解，但是其簡單、高效的特點使其獲得了廣泛的應用。透過以上三個典型問題的介紹，相信讀者可以更好地理解並掌握貪心演算法思想及其在C 中的實現。

以上是C++中的貪心演算法及其實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！