贪心算法 Greedy Algorithms

发表于 | 更新于 | 计算机技术

贪心算法（Greedy Algorithms）是一种简洁、高效、常见的优化算法。它是一种在每一步选择中都采取在当前看来是最好的选择，从而希望导致全局最优解的算法。贪心算法并不总是能找到全局最优解。贪心算法广泛应用于：霍夫曼编码、Dijkstra算法等。
贪心策略和动态规划非常相似。
0-1背包问题可以用动态规划解决，但是使用贪心算法时不能保证最优解。

贪心算法的关键在于贪心策略的选择，需要通过局部最优选择来构造全局最优解。

硬币找零(0-1背包问题)

注意贪心策略并不能保证0-1背包问题的最优解。

给定$n$种不同面值的硬币，每种硬币可以重复选取，再给定一个总金额$M$，求最少需要多少个硬币凑出目标金额。

cpp

/**
 * @brief 贪心算法的硬币找零问题
 * @param coins 硬币面值数组
 * @param amount 找零金额
 * @return 最少需要多少枚硬币
 * @note 假设coins数组是有序的
 */
int coin_change(vector<int>& coins, int amount)
{
    int n = coins.size() -1;
    int count = 0;
    while (amount > 0)
    {
        //找到最接近剩余金额且小于的硬币面值
        while ( n >0 && coins[n] > amount)
        {
            n--;
        }
        amount -= coins[n];
        count++;
    }
    return amount == 0? count : -1; //返回-1表示找不到足够的硬币
}

但是某些情况下，贪心算法并不能得到最优解，例如：
coins = {1, 20, 50}, amount =60，贪心算法只能找到(50+1 * 10)的组合，但是找不到(20 * 3)的组合。

分数背包问题

这是个典型的可以用贪心策略解决的问题。
给定$n$个物品（例如金砂等），第i个物品的重量为$wgt_{i-1}$，价值为$val_{i-1}$，背包最大容量为$W$，每个物品只能选一次但是可以选择物品的一部分，价值根据选择的重量比例计算。求背包中物品的最大价值。

cpp

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Item{
    public:
    int value, weight;

    Item(int v, int w) : value(v), weight(w) {}
};

/**
 * @brief 分数背包问题
 * @param wgt 物品的重量
 * @param val 物品的价值
 * @param W 背包的容量
 * @return 最大价值
 */
double fractionalKnapsack(vector<int>& wgt,vector<int>& val,int W)
{
    vector<Item> items;
    for(int i=0;i<wgt.size();i++)
        items.push_back(Item(val[i],wgt[i]));

    // 按照价值/重量的比例降序排序
    sort(items.begin(),items.end(),[](const Item& a,const Item& b){
        return (double)a.value/(double)a.weight > (double)b.value/(double)b.weight;
    });

    double res=0.0; // 最大价值
    int cur_w=0; // 当前背包的容量
    for(Item item:items){
        if(cur_w+item.weight<=W){
            res+=item.value;
            cur_w+=item.weight;
        }
        else{
            double part=(double)W/item.weight; // 装入的部分
            res+=item.value*part;
            break;
        }
    }
    return res;
}

int main()
{
    int W=50;
    vector<int> wgt={10,20,30};
    vector<int> val={60,100,120};
    double res=fractionalKnapsack(wgt,val,W);
    cout<<res<<endl;
    return 0;
}

活动选择问题

这是一个调度竞争共享资源的多个活动的问题，目标是选出一个最大的互相兼容的活动集合。
假设需要在工院256教室安排n个活动，工院256同一个时间内只能安排一个活动，有些活动的时间相互冲突，求尽可能多得安排活动数量。
从一系列活动中选择出数量最多且相互不冲突的活动，贪心策略是按活动结束时间排序后优先选择结束最早的活动，通过依次比较每个活动与已选活动的时间是否冲突，不断选择符合条件的活动，最终得到最多活动的安排方案。

cpp

// 定义活动结构体，包含活动开始时间和结束时间
struct Activity {
    int start;
    int end;
};

// 比较函数，用于按照活动结束时间对活动进行排序
bool compare(Activity a, Activity b) {
    return a.end < b.end;
}

// 贪心算法解决活动安排问题，返回最多能安排的活动数量
int activityScheduling(vector<Activity>& activities) {
    int n = activities.size();
    if (n == 0) return 0;

    // 对活动按照结束时间排序
    sort(activities.begin(), activities.end(), compare);

    int count = 1;  // 至少能安排一个活动，选择第一个活动
    int lastEnd = activities[0].end;  // 记录上一个选择的活动的结束时间

    // 依次遍历剩余活动，只要活动开始时间大于等于上一个活动的结束时间，就选择该活动
    for (int i = 1; i < n; i++) {
        if (activities[i].start >= lastEnd) {
            count++;
            lastEnd = activities[i].end;
        }
    }

    return count;
}

赫夫曼编码

赫夫曼编码 Huffman codes
前面的博客曾经提到过编码问题，赫夫曼编码通常能节省20%-90%的空间。
前缀编码：任意符号的编码都不是其他编码的前缀，这样在进行解码时就可以保证唯一且准确地还原出原始字符序列，不会出现歧义。
Huffman code 是一种构造最优前缀码的经典算法。
首先需要统计待编码的所有字符出现的频率，例如对于一段文本内容，统计每个字符出现的次数，然后计算出相应的频率（频率 = 字符出现次数 / 文本总字符数）。
然后创建节点集合：根据统计出的字符及其频率，为每个字符创建一个二叉树节点，节点中包含字符、频率以及左右子树指针（初始时左右子树都为空），将所有这些节点放入一个集合（通常可以用优先队列等数据结构来方便地管理这些节点，按照频率从小到大排序）。
从集合中取出频率最小的两个节点，创建一个新的节点作为这两个节点的父节点，父节点的频率等于两个子节点的频率之和，这个新的父节点代表了这两个字符组合后的一种 “中间状态”，把这个新的父节点放入集合中，然后重复上面的操作，逐步构建出一棵二叉树，这棵树就是哈夫曼树，其叶子节点对应着原始的字符，而从根节点到每个叶子节点的路径就可以用来生成相应字符的编码。
最后生成编码：从哈夫曼树的根节点开始，对每个叶子节点对应的字符进行编码，规定一种遍历方向与编码的对应规则，比如向左子树走编码为 0，向右子树走编码为 1（也可以反过来规定）。对于每个叶子节点（即每个字符），沿着从根节点到该叶子节点的路径，将经过的边对应的编码（0 或 1）依次记录下来，得到的这个 0 和 1 组成的二进制串就是该字符的哈夫曼编码。

编码过程：根据已经生成的编码表，对于要压缩的原始文本等数据，将每个字符替换为对应的编码二进制串，最终得到编码后的二进制数据，这个过程就是编码过程，实现了数据的压缩。解码过程：从编码后的二进制数据开头开始，按照构建哈夫曼树时规定的编码规则，从哈夫曼树的根节点出发，根据二进制数据中的 0 和 1 来决定是向左子树还是右子树走，当走到叶子节点时，就找到了对应的字符，然后继续从下一位二进制数据开始重复这个过程，直到所有的二进制数据都被解码完，这样就还原出了原始的字符序列。

这个问题在《数据结构与算法分析 C++描述》中有很易懂的解析。
伪代码如下：

txt

HuffmanCode(text):
    // 统计字符出现频率
    freq = CountFrequency(text)
    // 创建节点集合
    nodes = CreateNodes(freq)
    // 构建哈夫曼树
    huffmanTree = BuildHuffmanTree(nodes)
    // 生成编码表
    codeTable = GenerateCodeTable(huffmanTree)
    // 编码原始文本
    encodedText = EncodeText(text, codeTable)
    // 返回编码后的二进制数据

BuildHuffmanTree(nodes): // 构造哈夫曼树
    while nodes.size() > 1:
        // 找出频率最小的两个节点
        min1, min2 = FindMin(nodes)
        // 创建父节点
        parent = CreateNode(min1, min2)
        // 删除两个节点
        nodes.remove(min1)
        nodes.remove(min2)
        // 将父节点放入集合
        nodes.add(parent)
    return nodes.first()

最大切分乘积问题

给定正整数n，将其切分为至少两个正整数的和，求切分后所有整数的乘积最大是多少。

解析：这个问题和上面的不一样在于，它需要先做一个数学分析，分析的结论是需要优先拆出3。贪心策略即优先拆出3

设将正整数 n 拆分成 m 个正整数 a1, a2,..., am，使得它们的乘积 P = a1 × a2 ×...× am 最大，并且满足 n = a1 + a2 +...+ am。
我们可以通过简单的数学推导和分析来探讨这个问题：
对于数字 2 和 3 的比较：
把 6 进行拆分对比：拆分成 2 + 2 + 2，乘积为 2×2×2 = 8。拆分成 3 + 3，乘积为 3×3 = 9。可以发现对于相同的和，拆分成 3 的乘积更大，原因在于函数 y = x ^ (n / x)（n 为常数，表示总和，x 为拆分出的数字）在 x = 3 附近能取得相对较大的值（通过求导等数学方法可以进一步分析函数的单调性等性质来严格证明）。
对于大于 4 的数字：
假设我们有一个数字 k > 4，如果将其拆分成 k - 3 和 3，那么 (k - 3) × 3 = 3k - 9，而 k 本身对应的函数值 y = k，我们可以比较 3k - 9 和 k 的大小：令 3k - 9 > k，移项可得 2k > 9，也就是 k > 4.5。这意味着对于大于 4 的数字 k，拆分成 3 和 k - 3 后它们的乘积大于 k 本身，所以优先拆分出 3 是更有利的。

cpp

// 函数用于计算将正整数n切分后所有整数乘积的最大值
int integerBreak(int n) {
    if (n == 2) return 1;  // 2只能拆分成1 + 1，乘积为1
    if (n == 3) return 2;  // 3拆分成1 + 2，乘积为2
    int product = 1;
    while (n > 4) {
        product *= 3;  // 尽可能多地拆分出3
        n -= 3;
    }
    // 最后剩下的数字（可能是2、3、4）直接与之前的乘积相乘
    product *= n;
    return product;
}

参考资料