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

它与之前的算法类似。唯一的区别是，图 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, ... 阅读更多