淘宝上成都网站建设,网站建站公司哪家好,专业百度seo排名优化,需要注册的网站建设文章目录1. 贪心算法2. 应用2.1 找零钱2.2 区间覆盖2.3 霍夫曼编码霍夫曼编码完整代码1. 贪心算法
我们希望在一定的限制条件下#xff0c;获得一个最优解每次都在当前的标准下做出当下最优决策#xff08;整体不一定最优#xff09;#xff0c;做出的决策不可以后悔…
文章目录1. 贪心算法2. 应用2.1 找零钱2.2 区间覆盖2.3 霍夫曼编码霍夫曼编码完整代码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;//左端点相等取右端小的elsereturn 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];//存储选出来的区间人idint 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,qujianN);//对区间进行排序先按开始时间早排序一样早按占用时间少排前面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 k1; 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个byte1byte8bits存储这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-1priority_queuehtNode*,vectorhtNode*,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;//右边节点编码1pri_queue.pop();left pri_queue.top();left-code 0;//左边节点编码0pri_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-weightright-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;//输入的字符串编码后的总长度bitsfor(int i 0; i N; i)//遍历前N个字符节点求其编码{huffcode ;parent node[i];//从自己叶子节点开始向上找父节点直到rootcout i1 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 i1 ;cin w[i];//输入权值}huff.creatTree_outputCode(w);//将权值传入并生成Huffman树;生成霍夫曼编码打印出来return 0;
}
