贪心算法（Greedy Algorithm）之霍夫曼编码

Michael阿明

发布于 2021-02-20 10:47:26

4770

发布于 2021-02-20 10:47:26

文章被收录于专栏：Michael阿明学习之路

1. 贪心算法

我们希望在一定的限制条件下，获得一个最优解
每次都在当前的标准下做出当下最优决策（整体不一定最优），做出的决策不可以后悔，即不回溯，最终可以得到较为满意的解
贪心算法不追求最优解，节省时间，避免穷尽所有可能

2. 应用

2.1 找零钱

给定金额的找零，用最少张（枚）钱给顾客。（总是优先给大额的）

/**
 * @description: 贪心应用--找零钱
 * @author: michael ming
 * @date: 2019/6/28 22:02
 * @modified by: 
 */
#include <iostream>
#include <memory.h>
#include <math.h>
#define N 10
using namespace std;
void exchange(float money, float *rmb, int *amount)
{
    if(money < 0.1)
        return;
    int i, k = 0;
    for(i = 0; i < N; ++i)
    {
        money = round(money*10)/10.0;//四舍五入掉分
        k = money/rmb[i];
        amount[i] = k;
        money = money-k*rmb[i];
    }
}
int main()
{
    float rmb[N] = {100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1};
    int amount[N];
    while(1)
    {
        memset(amount,0,N*sizeof(int));
        float money;
        cout << "请输入要找的钱的金额：";
        cin >> money;
        money = round(money*10)/10.0;//四舍五入掉分
        cout << "找零结果如下(分位四舍五入)：" << endl;
        exchange(money,rmb,amount);
        int i = 0;
        while(i < N)
        {
            if(amount[i] != 0)
                cout << amount[i] << "个" << rmb[i] << " ";
            i++;
        }
        cout << endl;
        cout << "----------------------" << endl;
    }
}

2.2 区间覆盖

运用场景：任务调度，教师排课，学生活动室安排等

在上面图中再加入些区间数据[2,3];[-1,4],[5,12];[4,5]，代码实现如下：

/**
 * @description: 贪心算法--区间覆盖应用
 * (给定每个人可以在一个房间内活动的时间，要求让最多的人在这个房间活动，打印出这些人)
 * @author: michael ming
 * @date: 2019/6/29 23:34
 * @modified by: 
 */
#include <iostream>
#include <algorithm>
using namespace std;
struct Interval
{
    int left, right;
    bool operator<(const Interval &sel_idx) const
    {
        if(left == sel_idx.left)
            return right < sel_idx.right;//左端点相等，取右端小的
        else
            return left < sel_idx.left;//左端不等，取左端小的
    }
    bool belongto(int l, int r)//区间属于[l,r]的子集
    {
        return left >= l && right <= r;
    }
    bool absnotbelong(int l, int r)//两个区间完全无重叠
    {
        return left >= r || right <= l;
    }
};
int main()
{
    const int N = 10;//区间数量
    int left = 1, right = 10;//大区间左右端点（房间开放时间）
    int select[N];//存储选出来的区间（人）id
    int i, j, k, sel_idx = 0;
    for(i = 0; i < N; ++i)
    {
        select[i] = -1;
    }
    Interval qujian[N] = {{1,5},{2,4},{3,5},{5,9},{6,8},{8,10},{2,3},{-1,4},{5,12},{4,5}};//所有人的占用时间段
    sort(qujian,qujian+N);//对区间进行排序（先按开始时间早排序，一样早，按占用时间少排前面）
    for(i = 0; i < N; ++i)
    {
        if(qujian[i].left >= left && qujian[i].right <= right)//占用时间在开放时间内
        {
            while(sel_idx != 0 && !qujian[i].absnotbelong(qujian[select[sel_idx-1]].left,qujian[select[sel_idx-1]].right))
            {//如果有人占用了房间，一直找到第一个跟他时间不冲突的人
                ++i;
            }
            for(k = i, j = k+1; j < N; ++j)
            {//找到时间是不冲突那个人的最小子集的人
                if(qujian[j].belongto(qujian[k].left,qujian[k].right))
                {
                    k = j;
                }
            }
            select[sel_idx++] = k;//占用最短的那个人选出来
            i = k;//从这个人开始再往后找
        }
    }
    cout << "total selected " << sel_idx << " people, their time as following:" << endl;
    for(i = 0; i < N && select[i] != -1; ++i)
    {//打印被选出来的人的时间信息
        cout << i << ": [" << qujian[select[i]].left << ","
                << qujian[select[i]].right << "]" << endl;
    }
    return 0;
}

2.3 霍夫曼编码

假设有一个包含1000个字符的文件，每个字符占1个byte（1byte=8bits），存储这1000个字符一共需要8000bits，有没有更加节省空间的存储方式呢？
假设通过统计发现，这1000个字符中只包含6种不同字符，假设它们分别是a、b、c、d、e、f。而3个二进制位（bit）就可以表示8个不同的字符，a(000)、b(001)、c(010)、d(011)、e(100)、f(101)，所以，为了尽量减少存储空间，每个字符我们用3个二进制位来表示。那存储这1000个字符只需要3000bits就可以了，比原来的存储方式节省了很多空间。
还有没有更加节省空间的存储方式呢？
霍夫曼编码，考虑字符的出现频率，频率小的，用长编码，大的，用短编码，使得总体编码长度变短（且由于其编码方式，没有一个字符的编码是另一个的编码的前缀，避免了解码过程中的歧义）

霍夫曼编码完整代码

/**
 * @description: 贪心应用--霍夫曼编码
 * @author: michael ming
 * @date: 2019/6/30 23:53
 * @modified by: 
 */
#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <memory.h>

#define N 6		//字符集字符种数
using namespace std;
struct htNode//霍夫曼树节点
{
    char data;//数据类型
    char code;//数据存放的节点编码
    unsigned int weight;//数据权值
    htNode *parent, *lchild, *rchild;//连接节点指针
    htNode():data('/'),code('\0'),weight(0)
    {
        parent = lchild = rchild = NULL;
    }
};
class comp//优先队列比较函数
{
public:
    bool operator()(htNode* &a, htNode* &b)const
    {
        if(a->weight == b->weight)
            return a->data > b->data;
        return a->weight > b->weight;
    }
};

class HuffmanTree
{
public:
    htNode *root;//根节点指针
    htNode* node[2*N-1];//N个字符，霍夫曼树节点个数2*N-1
    priority_queue<htNode*,vector<htNode*>,comp> pri_queue;
    //优先队列中存放类指针时，第三个参数应该另写一个comp类，类内写operator()
    void creatTree_outputCode(int *w)
    {
        char ch = 'a';
        htNode *left, *right;
        for(int i = 0; i < N; ++i,++ch)
        {//生成前N个字符节点，输入权重，和字符信息
        	//并放入优先队列（权值小的优先）
            node[i] = new htNode();
            node[i]->weight = w[i];
            node[i]->data = ch;
            pri_queue.push(node[i]);
        }
        for(int i = N; i < 2*N-1; ++i)
        {//后面新生成的N-1个节点
            node[i] = new htNode();
            if(pri_queue.top()->data != '/')
            {//队首的节点不是新生成的，队首放右边
                right = pri_queue.top();
                right->code = '1';//右边节点编码1
                pri_queue.pop();
                left = pri_queue.top();
                left->code = '0';//左边节点编码0
                pri_queue.pop();//左右节点出队
            }
            else
            {//队首是新生成的节点，放左边
            	//（以上if-else保证新生成的节点总在左边）
                left = pri_queue.top();
                left->code = '0';
                pri_queue.pop();
                right = pri_queue.top();
                right->code = '1';
                pri_queue.pop();//左右节点出队
            }
            //新节点权值、上下连接指针对接
            node[i]->weight = left->weight+right->weight;
            node[i]->lchild = left;
            node[i]->rchild = right;
            left->parent = node[i];
            right->parent = node[i];
            pri_queue.push(node[i]);//新生成的节点入队
        }
        root = pri_queue.top();//最后还剩一个节点，是根节点
        creatHuffCode();
        for(int i = 0; i < 2*N-1; ++i)//释放资源
        {
        	delete node[i];
        }
    }
    void creatHuffCode()
    {
        htNode *parent;
        string huffcode;//霍夫曼编码
        int codelen = 0;//输入的字符串编码后的总长度bits
        for(int i = 0; i < N; ++i)//遍历前N个字符节点，求其编码
        {
            huffcode = "";
            parent = node[i];//从自己（叶子节点）开始向上找父节点，直到root
            cout << i+1 << " " << node[i]->data << " 的霍夫曼编码是: ";
            while(parent != root)//
            {
                huffcode.push_back(parent->code);//将路径中的编码汇成字符串
                parent = parent->parent;
            }
            reverse(huffcode.begin(),huffcode.end());//将最终的编码反转一下
            cout << huffcode << endl;
            codelen += huffcode.size()*node[i]->weight;//单字符code长*出现次数
        }
        cout << "该字符串的huffman编码长度为: " << codelen << " bits.";
    }
};

int main()
{
    HuffmanTree huff;
    cout << "请输入某字符串中" << N << "个字母abc...的权值（频率）：" << endl;
    int w[N];//权重
    for(int i = 0; i < N; ++i)
    {
        cout << i+1 << " ";
        cin >> w[i];//输入权值
    }
    huff.creatTree_outputCode(w);//将权值传入并生成Huffman树;生成霍夫曼编码，打印出来
    return 0;
}