C++中的贪心算法及其实现

### C++中的贪心算法及其实现

贪心算法（Greedy Algorithm）是计算机科学中一种重要的算法设计策略，其核心思想是通过局部最优选择逐步逼近全局最优解。与动态规划不同，贪心算法不依赖回溯或状态存储，而是基于“当前最优即全局最优”的假设，在每一步选择中做出看似最优的决策。这种特性使得贪心算法在解决特定问题时具有高效、简洁的优势，但也限制了其适用范围——仅当问题满足“贪心选择性质”和“最优子结构”时，才能保证正确性。

#### 一、贪心算法的核心概念

1. **贪心选择性质**：问题的全局最优解可以通过一系列局部最优选择（贪心选择）逐步构建。例如，在找零钱问题中，每次选择最大面额的硬币即为局部最优，最终能得到最少硬币数的解。

2. **最优子结构**：问题的最优解包含子问题的最优解。例如，在最小生成树问题中，整棵树的最小权重由各子树的最小权重构成。

3. **适用场景**：贪心算法适用于具有无后效性的问题（即当前选择不影响后续决策），如活动选择、霍夫曼编码、Dijkstra最短路径等。若问题存在后效性（如0-1背包问题），贪心算法可能失效。

#### 二、经典贪心问题与C++实现

##### 1. 活动选择问题

**问题描述**：给定n个活动，每个活动有开始时间`start[i]`和结束时间`end[i]`，要求选择最多数量的互不冲突活动。

**贪心策略**：按结束时间排序，每次选择结束最早且不与已选活动冲突的活动。

#include 
#include 
#include 

using namespace std;

struct Activity {
    int start, end;
};

bool compareEnd(Activity a, Activity b) {
    return a.end & activities) {
    sort(activities.begin(), activities.end(), compareEnd);
    
    vector selected;
    int lastEnd = -1;
    for (auto& act : activities) {
        if (act.start >= lastEnd) {
            selected.push_back(act);
            lastEnd = act.end;
        }
    }
    
    cout  activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}};
    selectActivities(activities);
    return 0;
}

**输出结果**：

Selected activities:
Start: 1, End: 4
Start: 5, End: 7
Start: 8, End: 9

##### 2. 找零钱问题

**问题描述**：给定硬币面额`coins[]`和目标金额`amount`，求最少硬币数（硬币可重复使用）。

**贪心策略**：每次选择最大面额的硬币，直到金额减至0。

#include 
#include 
#include 

using namespace std;

int coinChange(vector& coins, int amount) {
    sort(coins.begin(), coins.end(), greater());
    int count = 0;
    for (int coin : coins) {
        while (amount >= coin) {
            amount -= coin;
            count++;
        }
    }
    return amount == 0 ? count : -1; // 若无法精确找零，返回-1
}

int main() {
    vector coins = {1, 5, 10, 25};
    int amount = 63;
    int result = coinChange(coins, amount);
    cout 

**注意**：此贪心策略仅适用于特定硬币系统（如美国硬币面额）。对于非标准面额（如`{1, 3, 4}`找零6），需用动态规划。

##### 3. 霍夫曼编码

**问题描述**：为字符分配变长编码，使频繁字符的编码更短，减少总编码长度。

**贪心策略**：每次合并频率最小的两个节点，构建霍夫曼树。

#include 
#include 
#include 

using namespace std;

struct Node {
    char ch;
    int freq;
    Node* left, *right;
    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

void buildHuffmanCodes(Node* root, string code, unordered_map& huffmanCodes) {
    if (root == nullptr) return;
    if (!root->left && !root->right) {
        huffmanCodes[root->ch] = code;
    }
    buildHuffmanCodes(root->left, code + "0", huffmanCodes);
    buildHuffmanCodes(root->right, code + "1", huffmanCodes);
}

void HuffmanCoding(string text) {
    unordered_map freqMap;
    for (char ch : text) freqMap[ch]++;
    
    priority_queue, Compare> minHeap;
    for (auto& pair : freqMap) {
        minHeap.push(new Node(pair.first, pair.second));
    }
    
    while (minHeap.size() != 1) {
        Node* left = minHeap.top(); minHeap.pop();
        Node* right = minHeap.top(); minHeap.pop();
        Node* merged = new Node('$', left->freq + right->freq);
        merged->left = left;
        merged->right = right;
        minHeap.push(merged);
    }
    
    Node* root = minHeap.top();
    unordered_map huffmanCodes;
    buildHuffmanCodes(root, "", huffmanCodes);
    
    cout 

**输出结果**：

Huffman Codes:
a: 00
b: 01
c: 1

#### 三、贪心算法的局限性

1. **0-1背包问题**：贪心算法按价值密度排序可能无法得到最优解。例如，物品`{价值=60, 重量=10}`和`{价值=100, 重量=20}`，背包容量30时，贪心选择第一个物品两次（总价值120）优于选择第二个物品一次（总价值100），但若物品不可分割，贪心失效。

2. **依赖问题结构**：贪心算法的正确性高度依赖问题是否满足贪心选择性质。例如，在最小生成树问题中，Kruskal算法和Prim算法均基于贪心策略，但需证明其正确性。

#### 四、贪心算法的实现技巧

1. **排序预处理**：多数贪心问题需先对数据排序（如活动按结束时间、硬币按面额）。

2. **优先队列**：使用最小堆或最大堆高效获取当前最优元素（如Dijkstra算法中的最短路径更新）。

3. **贪心与回溯的对比**：贪心算法不保存中间状态，若发现当前选择错误也无法回溯，因此需严格验证问题是否满足贪心条件。

#### 五、C++中的贪心算法优化

1. **自定义排序**：通过重载比较函数或使用Lambda表达式实现灵活排序。

vector> items = {{5, 10}, {3, 5}, {1, 2}};
sort(items.begin(), items.end(), [](auto& a, auto& b) {
    return (double)a.first / a.second > (double)b.first / b.second; // 按价值密度排序
});

2. **贪心与动态规划的混合**：某些问题（如分数背包）可结合贪心与动态规划思想。

struct Item {
    int weight, value;
};

double fractionalKnapsack(vector& items, int capacity) {
    sort(items.begin(), items.end(), [](Item& a, Item& b) {
        return (double)a.value / a.weight > (double)b.value / b.weight;
    });
    
    double totalValue = 0;
    int remaining = capacity;
    for (auto& item : items) {
        if (remaining >= item.weight) {
            totalValue += item.value;
            remaining -= item.weight;
        } else {
            totalValue += item.value * ((double)remaining / item.weight);
            break;
        }
    }
    return totalValue;
}

#### 六、总结与扩展

贪心算法以其简洁性和高效性在算法设计中占据重要地位，但其正确性需严格验证。在C++实现中，排序、优先队列和自定义比较函数是关键工具。对于复杂问题，可结合动态规划或回溯思想设计混合算法。未来研究可探索贪心算法在分布式系统、机器学习（如特征选择）等新兴领域的应用。

关键词：贪心算法、C++实现、活动选择、霍夫曼编码、找零钱问题、贪心选择性质、最优子结构、优先队列、动态规划对比

简介：本文详细阐述了C++中贪心算法的核心概念、经典问题实现（如活动选择、找零钱、霍夫曼编码）及其局限性，分析了贪心算法的正确性条件，并提供了C++代码示例与优化技巧，最后总结了贪心算法的应用场景与扩展方向。