srcmini旅行售货员问题和贪婪算法
旅行售货员的问题由推销员和一组城市遵守。推销员必须从某个城市（例如家乡）开始访问每个城市, 然后返回同一城市。问题的挑战在于, 旅行售货员需要使旅行的总长度最小化。 假设城市为x1 x2 ….. xn, 其中成本cij表示从城市...
算法设计与分析 第14页
活动或任务计划问题
这是在单个处理器上最佳安排单位时间任务的争议, 其中每个作业都有最后期限, 如果错过了最后期限, 则必须支付罚款。 单位时间任务是一项工作, 例如要在计算机上紧急运行的程序, 而该程序恰好需要一个单位时间才能完成。给定单位任务的有限集合S,...
霍夫曼编码算法详细实现
示例：为以下一组频率找到最佳霍夫曼码： 解： 即 再次对于i = 2 同样, 我们采用相同的过程 因此, 最终输出为：
霍夫曼编码和贪婪算法
本文概述 前缀代码 构造霍夫曼码的贪婪算法 （i）可以使用霍夫曼码对数据进行有效编码。 （ii）它是一种广泛使用的有益数据压缩技术。 （iii）霍夫曼的贪婪算法使用每个字符出现频率的表来建立将每个字符表示为二进制字符串的最佳方式。 假设我们...
分数背包问题和贪婪算法
可以取项目的分数, 而不必对每个项目进行二进制（0-1）选择。 分数背包问题可以通过贪婪策略解决, 而0-1问题则无法解决。 解决分数问题的步骤 计算每件物品的每磅价值。 遵循贪婪策略, 我们尽可能选择每磅最高价值的物品。 如果该元素的供应...
活动选择问题和贪婪算法
活动选择问题是数学优化问题。我们的第一个例子是在几个挑战活动之间安排资源的问题。我们发现, 贪心算法为选择最大规模的手动兼容活动提供了一种精心设计且简单的方法。 假设S = {1, 2 …. n}是n个提议活动的集合。这些活动共...
贪婪算法介绍
本文概述 例 实现贪婪算法的步骤是 “贪婪方法可从许多选项中找到, 但你必须选择最佳选项。” 在这种方法中, 我们必须从许多现有方法中找出最佳方法/选项。 在这种方法/方法中, 我们专注于第一阶段并确定输出, 而不考虑未来。 此方法可能会或...
0/1背包问题：动态规划方法
本文概述 背包问题 0/1背包问题 0/1背包问题的示例 背包问题算法 背包问题 背包基本上是指背包。一袋给定的容量。 我们想在你的行李中装n件物品。 第一项价值为美元, 重量为磅。 尽可能承受有价值的负载, 但不能超过W磅。 vi wi ...
最长公共序列算法
最长公共序列的示例 示例：给定两个序列X [1 … m]和Y [1 ….. n]。找到两者的最长共同子序列。 那是： 步骤4：构建LCS：初始调用为PRINT-LCS（b, X, X.length, Y.length...
最长公共序列（LCS）和动态规划
给定序列的子序列就是给定序列, 其中某些元素被省略。 给定两个序列X和Y, 如果Z是X和Y的子序列, 则我们说序列Z是X和Y的公共序列。 在最长的公共子序列问题中, 我们给定两个序列X =（x1 x2 …. xm）和Y =（y1...