链接：https://pan.baidu.com/s/1qs2WGcjbw1k-Sj7c1HfJyw 

提取码：a10z

心算法模型

 

背包问题

背包问题就是有若干物品，每个物品有自己的价值υ1, υ2, υ3 … υn和重量ω1,  ω2, ω3 … ωn。背包有总重量∁。问题就是怎样将背包装的最大价值。背包问题也分很多种，贪心算法解决的是物品可以拆分的背包问题（就是物品可以分成几份装入）。这个问题用贪心还是比较好解决的。

贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。此问题就是将每次的放入看成每一步，要想解决问题，就是将每一步都放入最优解。也就是说，每一次的放入都要放入最佳的选择。讲到这里，就要说一说最佳的选择，每一次的放入的最佳的选择就是每次放入的物品都是剩余的物品中价值最大且质量最小的，这里就要引入一个物品的属性，物品的权重值。物品的权重值就是指物品的价值除以物品的质量。所以，本问题的每一次的最佳选择就是每次都选出权重值最大的物品。

 

单源最短路径问题

单元最短路径：给定顶点到其它任一顶点的最短路径。

一个有向图G，它的每条边都有一个非负的权值c[i，j]，“路径长度”就是所经过的所有边的权值之和。对于源点需要找出从源点出发到达其他所有结点的最短路径。

E.Dijkstm发明的贪婪算法可以解决最短路径问题。算法的主要思想是：分步求出最短 路径，每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪 婪准则选取：在未产生最短路径的顶点中，选择路径最短的目的顶点。

设置顶点集合S并不断作贪心选择来扩充这个集合。当且仅当顶点到该顶点的最短路径 已知时该顶点属于集合S。初始时S中只含源。

设u为G中一顶点，我们把从源点到u且中间仅经过集合S中的顶点的路称为从源到11 特殊路径，并把这个特殊路径记录下来（例如程序中的dist[i，j])。

每次从V-S选出具有最短特殊路径长度的顶点u，将u添加到S中，同时对特殊路径长度进行必要的修改。一旦V=S，就得到从源到艽他所有顶点的最短路径，也就得到问题的解。

 

贪心算法的问题

 

贪心算法的优缺点

优点：一个正确的贪心算法拥有很多优点，比如思维复杂度低、代码量小、运行效率高、 空间复杂度低等，是信息学竞赛中的一个有力武器，受到参赛选手们的青睐。

缺点：贪心法的缺点集中表现在其“非完美性”。通常很难找到一个简单可行并 且保证正确的贪心思路，即使我们找到一个看上去很正确的贪心思路，也需要严格的正确性证明。这往往给我们直接使用贪心算法带来了巨大的困难。往往不能保证求得的最后解是最佳的；同时贪心算法也不能用来求最大或最小解的问题，只能求满足某些约束条件的可行解的范围。

 

 

经典贪心算法

 

普里姆算法

普里姆算法概览

普里姆算法（Prim's algorithm），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。