夏令营提高班贪心算法_第1页
夏令营提高班贪心算法_第2页
夏令营提高班贪心算法_第3页
夏令营提高班贪心算法_第4页
夏令营提高班贪心算法_第5页
已阅读5页，还剩14页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、贪心算法山东师大附中陈键飞贪心贪心法是沿着一种固定的策略一直走下去的算法与动态规划和搜索的区别是，动态规划和搜索在一个阶段都会考虑所有可能出现的状态，而贪心只需要知道哪个状态是最优可以用贪心的条件是满足：每步都最优，总结果也最优小例子部分背包问题：有一个容量W的背包，有N种物品，每种有Wi单位的体积和Vi单位的价值你可以把一件物品的一部分装进背包，怎么使总价值最大？01不能W=9W1=7 , V1 = 14W2=5 , V2 = 9W3=4 , V3 = 7例题1有n个人, 第i个人重量为wi。每艘船的载重量均为C, 最多乘两个人。用最少的船装载所有人。让最轻的人和能坐下的最重的人坐例题2有1

2、N的一个排列，每次可以交换任意两个，用最少的次数将它们变成1N过河有N个人要过一个河，有一个最多载两人的小船，每个人有一个过河时间，如果两个人过河，则用时是较慢的那个人的用时，问最少需要多长时间所有人都过河。如A,B,C,D 1,2,5,8AB2 A1AC5 A1AD8AB2 A1C D 8 B 2A B 2区间上的问题有N个区间，选择最多的区间，使它们不互相重叠区间上的问题有N个闭区间，选最少的点，使得每个区间都至少包含一个点有N个闭区间，选最少的整点，使得每个区间都至少包含k个点区间上的问题有N个闭区间Ai,Bi，选最少的区间覆盖一条指定线段S,THuffman编码给定N个字符每个字符的出

3、现频率Ci，给每个字符编一个二进制码，不能有一个字符的编码是另一个的前缀。问编码后的文本最短多长。如aaaabbbc则a=0，b=10，c=11则 Huffman编码Huffman树怎样构造？每次取出现频率最低的两个字符将它们的编码一个在最后加上0，一个加上1然后合并成同一个abc0101Huffman编码Ca=9 , Cb=5 , Cc=10 , Cd=1 , CE=6 , CF=10abcdef9510166Huffman编码需要证明什么？频率最小的两个点一定是兄弟，且深度最大为什么深度最大的点一定有兄弟？每个点一定有两个儿子合并果子有N堆果子，每堆重量是Wi，合并两堆果子i/j的费用是Wi+Wj，用最小的费用合并所有果子流水作业调度问题有n个作业要在两台机器M1和M2组成的流水线上完成加工。每个作业i都必须先花时间ai在M1上加工，然后花时间bi在M2上加工。确定n个作业的加工顺序，使得从第一个作业在机器M1上加工开始到最后一个作业在机器M2上加工为止总时间最少。流水作业调度问题直观上看，应该让M1不停地工作，而M2的空闲时间尽量少设N1为a b的作业集合，N2为a b的作业集合将N1中的作业照a非减序排序，N2中的作业按照b非增序排序，则N1作业接N2作业构成最优顺序。一个

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论