TIP

贪心这个词在我们的生活中随处可见,贪心像是大自然万物特有的,而人将这发展到了极致。得到了想要的东西,还想要更好的东西,永无止境,所以又有一个词:知足常乐。只不过现在所有你想要的都摆在了你的面前,你要怎么选择呢?

# 什么是贪心算法

贪心算法顾名思义,就是一个字“贪”,就像小时候吃饭一样,满桌子的菜,总是先吃你最爱吃的,然后爱吃的吃完了怎么办呢,在吃你第二爱吃的······直到肚子里吃饱。这个是一个生活中很有意思的一个场景。简单的说,贪心算法,对于一个特定的问题,选择一定的策略,按照这个策略一步步的执行下去,直到得到结果。这个策略一定是最优的,但是得到的结果却不一定是最优的,所以贪心算法有它的局限性。

# 贪心算法适用的范围

适用范围我就用举例子的方式说吧,有一个小偷,背着一个背包去商店抢东西,每个物品都包括两部分,价值和重量,问这个这个小偷在背包不破的情况下最多可以拿几件物品。这个是背包问题的一个转化,以前让求最大的价值,现在让求最多可以装多少个物品。那么我现在就把所有的物品按照重量的顺序从小到大排序,每次都选择一个重量最轻的,然后判断这个物品的重量是否大于我背包剩余的容量,如果不大于,那么我就可以放进去,直到放不进去为止,很显然,这样下来我求的结果一定是最优的。 还有就是买东西给钱的问题,首先就假设不管要给多少钱,我的钱数一定都是够的,要不然就会出现所有的钱数加起来也不够给的情况。现在去超时买东西,花了123块钱,现在你的身上有100502010521这几种纸币,假设每种纸币个数都无限,现在你想要用最少的纸币数来给钱,那么该怎么给呢?肯定是每次从身上掏出一样小于所付钱数的最大面值,按照这样的策略,每次也会得到最优的结果,就算是纸币数有限也是可以的,因为我每次选择的都是最优的啊。

# 数据结构中的贪心算法

数据结构中的最优前缀码、最小生成树和单源最短路径等问题都是贪心算法的典型应用

# 最优前缀码就是哈夫曼编码

这个算法我也是在电脑上自己动手实现过,整段代码也是将近有两百行,实现了可以将一篇文章按照每个字符出现的频率编码,而且有了这个编码结果也可以实现解码的。为了方便我是以英文做的,貌似汉语弄得意义不大,英文总共就有26,加上一些标点符号也没有几个。下面就把大致框架放在下面吧

typedef struct Node{ //保存每个节点的内容,存储
    int weight;
    int parent;
    int lchild;
    int rchild;
    char car;
} Node;
void selectMin(Node a[],int k,int &s1,int &s2){ //每次都选择两个最小的
}
void Huffmantree(Node huffmantree[],int n,int x[],int &t){
    // 包括了这棵树的初始化,以及中间值的一些转化
}//哈夫曼编码的核心过程
void HuffmanCode(Node huffmantree[],int t){
}//这个是解码的过程
void dfs(Node huffmantree[],int m,int temp){
    //将所建立的哈弗慢树它的字符用01来表示,用递归寻找树的叶子节点
}   
void Code(int t){
}
int main()
{
    int x[27]= {0};//x的下标代表26个英文字母
    int t=0;//t是代表有多少种不同的字符
    Node *huffmantree=new Node[2*27-1];
    Huffmantree(huffmantree,27,x,t);//哈夫曼建树过程
    dfs(huffmantree,2*t-2,temp); //深度遍历算出他们的路径
    Code(t);//编码
    HuffmanCode(huffmantree,t);
    return 0;
}