问题标签 [greedy]

我需要验证一个范围。输入格式如下：

我正在使用以下正则表达式：

当用户输入"anydate between 20100101 ~~ 20100101 and test1"失败时，它会捕获 until test1。

如何使我的正则表达式不那么贪婪并且只捕获直到20100101？

我对下面提到的算法问题有困难：

一个港口有一个三车道的渡轮，在它前面有N辆车的队列。他们每个人都有以厘米为单位的指定长度。我们也知道渡轮的长度 (L)。我们必须提出一种算法，该算法能够从队列中装载最大数量的汽车。每辆车都可以选择走三个车道之一：左、中或右。必须按顺序处理汽车 - 对于每辆汽车（从前面开始），我们必须决定它将驶入哪条车道。如果在我们完成时没有足够的空闲空间让汽车排在队列的前面。剩余的汽车等待下一个渡轮。

贪心方法（首次拟合）并不是在每种情况下都是最有效的（例如，如果 L 为 5 并且我们有队列 5 2 2 3 3）。因此，如果我们将其视为动态规划问题，我试图找出解决方案是什么。我仍然试图找到任何，但我知道的所有动态算法（尤其是来自算法简介）似乎都不适合这个问题。

提前感谢您的任何建议。:)

我对一种算法有疑问。

给定 n 个盒子，每个盒子都有固定的重量和强度（均以 kg 为单位）。Box的强度告诉我们它可以承受的最大重量是多少。我们必须形成最高的一堆给定的盒子（每个盒子都有相同的高度）。您应该提出一种算法，该算法将始终给出最佳解决方案，即 k 个框的最长序列 (k <= n)。

好吧，这是我已经想出的解决方案：

1. 首先，我们按重量对所有盒子进行分类（最重的在底部）并形成一堆。
2. 其次，我们按强度对那堆进行排序（最强的在底部）。
3. 然后，对于每个盒子，从底部开始，只要它的强度允许，我们尝试将其拉到底部。
4. 最后，我们必须弄清楚必须从顶部移除多少个盒子，这导致下面的一些盒子承载的重量比它们所能承受的重得多。

看起来这个算法工作得很好，但我不确定它是否总是给出最佳解决方案 - 可能没有。我一直想知道动态解决方案，类似于背包问题的解决方案，但我不确定是否可以通过这种方式解决。我的问题似乎没有最佳子结构。

预先感谢您的任何帮助。:)

我有一个正则表达式来匹配如下所示的文件名：

我想提取名称和子名称，而不需要任何附加数据。我能够很好地提取数据，给我错误的问题是v4部分（它是一个版本标记，它是 av 和它后面的一个数字，它不包含在任何地方），我想排除它但它提取它连同子名...

我的正则表达式如下所示：

我尝试做这样的事情，但它只能?在没有“”结尾的情况下工作(?:v\d+ )?，然后它无法匹配没有版本的文件名：

我如何使它工作？

对于分隔符（例如<和>）之间匹配文本的常见问题，有两种常见模式：

• 使用贪心*或+量词的形式START [^END]* END，例如<[^>]*>，或
• 在表格中使用惰性*?或+?量词START .*? END，例如<.*?>.

有什么特别的理由偏爱其中一个吗？

以下问题取自Problems on Algorithms (Problem 653)：

你得到一个数字矩阵。找到一个 O(n log n) 算法，该算法对数组中的行进行置换，使得数组的任何一列都不包含比 ⌈√n 长的递增子序列（可能不包含连续的数组元素）。⌉

我不知道如何解决这个问题。我认为它可能会使用某种分而治之的重复，但我似乎找不到。

有谁知道如何解决这个问题？

我想修改 Prim 的算法，以便它找到最大生成树如何做到这一点

我正在阅读有关“贪婪”算法的教程，但我很难发现它们解决真正的“顶级编码器”问题。

如果我知道可以使用“贪婪”算法解决给定问题，那么编写解决方案非常容易。但是，如果我没有被告知这个问题是“贪婪的”，我就无法发现它。

用“贪心”算法解决的问题的共同属性和模式是什么？我可以将它们简化为已知的“贪婪”问题之一（例如 MST）吗？

我有一个关于测试评论的问题，即“以下哪项是通过贪婪方法启发式解决的？”

A. 未加权间隔调度

B. 0/1 背包

C. 分数背包

D. 霍夫曼密码

我能够将其缩小到 A、C 或 D，因为我知道 0/1 背包使用动态编程。我最好的猜测是 C，因为我认为 A 和 D 可以使用贪心算法最佳地解决。

这个对吗？

我无法弄清楚动态硬币更换问题的最后一段代码。我已经包含了下面的代码。

我想不通最后一个else。那时我应该只使用贪心算法，还是可以根据表中已有的值计算答案？我一直在努力理解这个问题，我想我已经很接近了。该方法通过创建一个表并使用存储在表中的结果来解决更大的问题而不使用递归来找到产生一定数量的零钱所需的最小硬币数量。