Chapter 4 贪心

为什么需要贪心算法

在算法设计中，贪心算法是一种通过在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法通常用于解决优化问题。

贪心算法的核心思想是通过局部最优选择来达到全局最优解。它适用于那些具有“最优子结构”和“贪心选择性质”的问题。

与动态规划的区别：动态规划通常用于解决具有重叠子问题和最优子结构的问题，而贪心算法则侧重于通过局部最优选择来构建全局最优解。动态规划通常需要保存中间结果，而贪心算法则不需要。贪心不依赖子问题的解决策，而动态规划依赖。

贪心算法的步骤

选择策略：确定在每一步中如何选择当前的最优解。这通常涉及定义一个贪心选择标准。
可行性检查：确保每次选择都不会违反问题的约束条件。
构建解：通过不断应用选择策略，逐步构建最终的解决方案。
验证最优性：在某些情况下，可能需要证明贪心选择确实能导致全局最优解。

证明贪心选择性质的方法：

存在整体最优解
修改最优解，是其以贪心选择开始
该问题转化为规模更小的相同形式的子问题
数学归纳法证明每一步都如此

k = 1 时，该解就是最优解 k > 1 时，令活动1替换活动k（因为活动1结束时间最早），得到新的解仍然是最优解

反证法？

最优子结构性质证明的方法：

假设一个问题的最优解包含其子问题的解。
通过构造或反证法证明，如果子问题的解不是最优的，那么整个问题的解也不会是最优的。

纸币找零问题

假设你是一个收银员，需要找零给顾客。你有面值为1元、5元、10元和20元的纸币。顾客需要找零37元。使用贪心算法，你会选择尽可能大的面值，直到达到所需的金额。

选择一张20元纸币，剩余17元。
选择一张10元纸币，剩余7元。
选择一张5元纸币，剩余2元。
选择两张1元纸币，剩余0元。

最终，你会使用1张20元、1张10元、1张5元和2张1元纸币来找零37元。

为什么贪心算法在这个问题中有效？因为每次选择最大的面值都能确保剩余金额最小，从而减少了总的纸币数量。

但是！如果纸币的面值是1元、3元和4元，顾客需要找零6元。使用贪心算法：

选择一张4元纸币，剩余2元。
选择两张1元纸币，剩余0元。

最终，你会使用1张4元和2张1元纸币，共3张纸币。 然而，最优解是使用两张3元纸币，共2张纸币。 这说明贪心算法并不总是能找到最优解。 但是可以找到近似解。

活动选择问题

活动选择问题是指在给定一组活动的开始和结束时间的情况下，选择尽可能多的互不冲突的活动。贪心算法在这个问题中表现出色。

排序活动：首先，根据活动的结束时间对活动进行排序。
选择活动：选择第一个活动，然后选择下一个与已选择活动不冲突且结束时间最早的活动，重复此过程直到没有更多活动可以选择。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Activity {
    int start;
    int end;
};
bool compare(Activity a1, Activity a2) {
    return a1.end < a2.end;
}
void greedyActivitySelector(vector<Activity>& activities) {
    sort(activities.begin(), activities.end(), compare);
    int n = activities.size();
    cout << "Selected activities: " << endl;
    int lastEndTime = -1;
    for (int i = 0; i < n; i++) {
        if (activities[i].start >= lastEndTime) {
            cout << "Activity(" << activities[i].start << ", " << activities[i].end << ")" << endl;
            lastEndTime = activities[i].end;
        }
    }
}
int main() {
    vector<Activity> activities = { {1, 3}, {2, 5}, {4, 6}, {6, 7}, {5, 8}, {8, 9} };
    greedyActivitySelector(activities);
    return 0;
}

复杂度分析：排序活动的时间复杂度为O(n log n)，选择活动的时间复杂度为O(n)，因此总的时间复杂度为O(n log n)。

霍夫曼编码

霍夫曼编码是一种用于无损数据压缩的贪心算法。它通过为频率较高的符号分配较短的编码，而为频率较低的符号分配较长的编码，从而实现数据的压缩。

构建优先队列：将所有符号及其频率插入一个优先队列（最小堆）。
构建霍夫曼树：重复以下步骤直到队列中只剩一个节点：
- 从队列中取出两个频率最小的节点。
- 创建一个新节点，其频率为这两个节点频率之和，并将这两个节点作为新节点的子节点。
- 将新节点插入队列中。
生成编码：从根节点开始，为每个左子节点分配一个“0”，为每个右子节点分配一个“1”，直到到达叶节点，生成每个符号的编码。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;
    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};
struct compare {
    bool operator()(Node* l, Node* r) {
        return l->freq > r->freq;
    }
};
void generateCodes(Node* root, string str, unordered_map<char, string>& codes) {
    if (!root) return;
    if (!root->left && !root->right) {
        codes[root->ch] = str;
    }
    generateCodes(root->left, str + "0", codes);
    generateCodes(root->right, str + "1", codes);
}
void huffmanCoding(vector<pair<char, int>>& frequencies) {
    priority_queue<Node*, vector<Node*>, compare> minHeap;
    for (auto& freq : frequencies) {
        minHeap.push(new Node(freq.first, freq.second));
    }
    while (minHeap.size() > 1) {
        Node* left = minHeap.top(); minHeap.pop();
        Node* right = minHeap.top(); minHeap.pop();
        Node* newNode = new Node('\0', left->freq + right->freq);
        newNode->left = left;
        newNode->right = right;
        minHeap.push(newNode);
    }
    Node* root = minHeap.top();
    unordered_map<char, string> codes;
    generateCodes(root, "", codes);
    cout << "Huffman Codes: " << endl;
    for (auto& code : codes) {
        cout << code.first << ": " << code.second << endl;
    }
}
int main() {
    vector<pair<char, int>> frequencies = { {'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45} };
    huffmanCoding(frequencies);
    return 0;
}