在这篇文章中，我们将了解贪婪算法和动态规划方法之间的区别。贪婪算法它是一种算法范例，逐步构建解决方案。选择下一步的方法是，它能带来最明显和直接的好处。涉及选择局部最优值的问题将有助于选择问题的全局最优值/解决方案。这些都是与贪婪算法相关的问题。不能保证贪婪算法会产生最优解。在问题的每个阶段都会做出最优选择，即局部最优解。它……阅读更多

它与之前的算法类似。唯一的区别在于，图G(V, E) 由邻接表表示。邻接表表示的时间复杂度为 O(E log V)。输入和输出输入：成本矩阵：输出：边：A--B 和成本：1 边：B--E 和成本：2 边：A--C 和成本：3 边：A--D 和成本：4 边：E--F 和成本：2 边：F--G 和成本：3 总成本：15算法prims(g: 图，开始)输入 - 图 g 和名为“开始”的种子顶点输出 - 添加边后的树开始 创建两个集合 B、N 将起始节点添加到 B ... 阅读更多

给定一个连通图 G(V, E)，并且给出每条边的权重或成本。Prim 算法将找到图 G 的最小生成树。这是一种增量树方法。该算法需要一个种子值来启动树。种子顶点被扩展以形成整棵树。这个问题将使用两个集合来解决。一个集合保存已选择的节点，另一个集合保存尚未考虑的项。从种子顶点开始，它根据最小边成本获取相邻顶点，从而通过……阅读更多

给定到达时间和离开时间的列表。现在问题是找到铁路所需的最小站台数量，因为没有火车等待。通过对所有时间进行排序，我们可以很容易地找到解决方案，这将很容易跟踪火车何时到达但尚未离开车站。这个问题的时间复杂度为 O(n Log n)。输入和输出输入：到达时间和离开时间的列表。到达：{900, 940, 950, 1100, 1500, 1800} 离开：{910, 1200, 1120, 1130, 1900, 2000} 输出：所需的最小站台数：3算法minPlatform(arrival, departure, int n)输入 - …阅读更多

给定一个硬币列表 C(c1, c2, ……Cn) 和一个值 V。现在问题是用最少的硬币数量来凑成值 V。注意 - 假设有无限数量的硬币 C在这个问题中，我们将考虑给定的一组不同硬币 C{1, 2, 5, 10}，每种类型的硬币数量无限。为了凑成所需的值，我们将尝试取任何类型的最少数量的硬币。例如，对于值 22 - 我们将选择 {10, 10, 2}, …阅读更多

在之前的霍夫曼编码问题中，频率未排序。如果给定频率列表已排序，则分配代码的任务将更有效。在这个问题中，我们将使用两个空队列。然后为每个唯一字符创建一个叶节点，并将其按频率递增的顺序插入队列中。在这种方法中，算法的复杂度为 O(n)。输入和输出输入：按排序顺序排列的不同字母及其频率 字母：{L, K, X, C, E, B, A, F} 频率：{1, 1, 2, 2, 2, 2, 3, 4} 输出：字母的代码 L：……阅读更多

霍夫曼编码是一种无损数据压缩算法。在这个算法中，将可变长度代码分配给不同的输入字符。代码长度与字符的使用频率有关。最常用的字符具有最短的代码，而最不常用的字符具有更长的代码。主要有两个部分。第一个是创建霍夫曼树，另一个是遍历树以查找代码。例如，考虑一些字符串“YYYZXXYYX”，字符 Y 的频率大于 X，而字符 Z 的频率最小。因此，Y 的代码长度小于……阅读更多

给定一个图 G(V, E) 及其邻接表表示，并提供一个源顶点。Dijkstra 算法用于查找从源顶点到图 G 的任何其他顶点的最小最短路径。为了解决这个问题，我们将使用两个列表。一个是存储已被认为是最短路径树的顶点，另一个将保存尚未考虑的顶点。在算法的每个阶段，我们找到未考虑的顶点，并且该顶点与源的距离最小。另一个列表用于保存前驱节点。使用……阅读更多

给定 n 个不同的活动及其开始时间和结束时间。选择由一个人解决的最大活动数量。我们将使用贪婪方法来查找下一个活动的完成时间在剩余活动中最小，并且开始时间大于或等于最后一个所选活动的完成时间。如果列表未排序，则此问题的时间复杂度为 O(n log n)。如果提供排序列表，则复杂度将为 O(n)。输入和输出输入：具有开始时间和结束时间的不同活动的列表。{(5,…阅读更多