貪心演算法是一種常用的演算法思想,在許多問題中都有著廣泛的應用。其核心思想是在做出每一步的決策時,只考慮眼前最優解,而不考慮長遠的影響。
在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中文網其他相關文章!