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

它类似于之前的算法。这里唯一的区别是，图 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(到达，离开，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，... 阅读更多