锐客网

  1. 首页 > 睿知 > it技术 > >

贪心策略java实现代码 贪心策略是什么

IT技术算法

哈夫曼编码（贪心算法）参考： 哈夫曼编码
哈夫曼编码是一种十分有效的编码方法贪心策略java实现代码，广泛应用于 数据压缩 中
通过采用 不等长 的编码方式，根据 字符频率的不同，选择 不同长度的编码，对频率 越高 的字符采用 越短 的编码实现数据的高度压缩 。
这种对频率越高的字符采用越短的编码来编码的方式应用的就是贪心算法的思想 。
下面看一个例子：
假如我们有一个包含1000个字符的文件 ， 每个字符占1个byte(1byte=8bits)，则存储这100个字符一共需要8000bits 。这还是有一些大的
那我们统计一下这1000个字符中总共有多少种字符，原来需要8bit来表示一个字符，如果使用更少的位数来表示这些字符，则可以减少存储空间 。
假设这1000个字符中总共有a、b、c、d、e、f共6种字符，使用使用3个二进制位来表示的话 ， 存储这1000个字符就只需要3000bits，比原来更节省存储空间 。
或许还可以再压缩一下：
根据字符出现的 频率 给与字符 不等长 的编码，频率越高的字符编码越短，频率越低的字符编码越长 。
它不能像等长编码一样直接按固定长度去读取二进制位，翻译成字符，为了能够准确读取翻译字符，它要求一个字符的编码不能是另外一个字符的前缀 。
假设a、b、c、d、e、f这6个字符出现的频率依次降低 ， 则我们可以给与他们这样的编码
假如字符的出现频率如图所示，按照这样的编码表示的话，总位数如图，一共2100bits，更加节省空间了
贪心策略：频率小的字符，优先入队 。
步骤：
1.将每一个字符作为节点，以出现频率大小作为权重，将其都放入 优先队列 中（一个最小堆）贪心策略java实现代码；
2.每次出队两个节点并创建一个父节点，使其权值为刚刚出队的节点的权值和，并且为两个节点的父节点（合并） 。然后将这个树入队 。
3.重复操作2 ， 直到队列中只有一个元素（此时这个元素表示形式应该为一个树）时 ， 完成创建 。
创建好了树，该怎么编码呢？
我们对一个哈夫曼树，从父节点开始的所有节点，往左边标0，右边标1 。那么到达叶子节点的顺次编码就可以找到了 。
C：字符集合
Q：优先队列
EXTRACT-MIN：传入一个队列，出队最小的元素
INSERT：将z插入到Q中
当for循环结束之后 ， 此时队列中只有一个元素，就是我们需要的哈夫曼树，最后返回此树即可 。
假设T树已经是一个最优的树，假设x、y的频率小于等于最低处的a、b，然后交换x、a，y、b 。
计算代价是否发生变化 。
比如这里比较 T 变成 T ’ 后代价是否变化，发现代价变小或不变 。
同理T’到T’’，又因为T本来假设就是最优的，所以只能相等
所以T’’也应该符合条件，即贪婪算法 ， 每次取最小的两个节点出来这种做法是正确的
找零钱问题 [贪心算法](java实现）public getMin{
public int MinNumber=0;
public int findMax(int[] a){
for(int i=0;ia.length;i++){
if(a[i]==0) return a[--i];
}
return a[a.length-1];
}
public boolean Compare(int a,int b){
public boolean flag=true;
if(ab)flag=flase;
return flag;
}
public int getMinNumber(int[] M,int Money){
int[] findM=new int[M.length];
int index=0;
for(int i=0;iM.length;i++){
boolean f = this.Compare(M[i],money)
if(f)findM[index++]=M[i];
}
int max = this.findMax(findM);
MinNumber++;
if((Money-max)!=0) {
getMinNumber(M,Money-max)

推荐阅读


上一篇：mongodb建立索引树，mongodb如何建立索引

下一篇：包含phpajaxmysql实时的词条