问题标签 [greedy]

我有以下 Python 正则表达式：

对于以下文本：

正在返回的组是：
(1) 所需组 #1
(2) 不需要的组 #2
(3) 不需要的组 #3
(4) 不需要的组 #4

为什么会这样？因为我得到了 Desired Group #1 并使用非贪婪的 .+? 使用 flags=re.DOTALL，我希望它不会跳过任何我想要的组 2-4。

提前致谢。

更新：

最终使用 xml.etree.ElementTree 如下：

发现以下链接对 NCBI BLAST 特定的 XML 解析示例有用： http ://www.dalkescientific.com/writings/NBN/elementtree.html

我是算法新手，目前正在使用 youtube 视频教程/讲座和一本书进行学习，我首先观看视频，然后阅读这本书，最后尝试书中的一个问题，以确保我正确地学习了该主题。我目前正在使用贪婪算法，这非常令人困惑。

书中有各种问题，但我无法理解和回答特定问题。

首先它给出的问题是（我刚刚复制了文本）。

有一组 n 个大小为 {x1; x2;..... xn} 和容量为 B 的 bin。所有这些都是正整数。尝试找到这些对象的子集，使它们的总大小小于或等于 B，但尽可能接近 B。

所有对象都是一维的。例如，如果对象的大小为 4、7、10、12、15 和 B = 20，那么我们应该选择总大小为 19 的 4 和 15（或等效地，7 和 12）。对于以下每个贪心算法，通过创建一个反例来证明它们不是最优的。尝试使您的示例尽可能糟糕，其中“不良”是通过最佳解决方案和贪婪解决方案之间的比率来衡量的。因此，如果最佳解决方案的值为 10，而贪心解决方案的值为 5，则比率为 2。

我该如何为以下内容执行此操作？

1) 始终选择尺寸最大的对象，以使该对象和已选择的所有其他对象的总尺寸不超过 B。对其余对象重复此操作。

我有以下字符串：

我需要创建正则表达式模式并在“src”首次出现之前获取所有内容。

我试过这样使用，.+(src)但据我所知，我需要减少贪婪，有人可以帮忙吗？

我正在寻找用 java 实现的 GSAT 和 SA-SAT 算法。有人知道吗？谢谢你。

在游戏 Hangman 中，贪心字母频率算法是否等同于最佳获胜机会算法？

为了更好地猜测正确答案，是否有值得牺牲剩余生命的保护？

进一步澄清问题：

• 要猜测的选定单词已从已知字典中获取。
• 你有 N 条生命，因此必须最大限度地猜测单词中的所有字母而不犯 N错误（即你可能有无限数量的正确猜测）。
• 为了这个练习，字典中的每个单词都有相等的概率（即随机选择单词）
  • 一个更难的练习是想出一个对抗恶意的、无所不知的选词者的策略（我不是在这里问这个）

动机：这个问题的灵感来自于http://www.datagenetics.com/blog/april12012/index.html上的有趣讨论

他们提出了一种算法来优化解决文字游戏“Hangman”。

他们的策略可以总结如下（为澄清而编辑）：

• 我们可以假设这个词是从特定的字典中提取的
• 我们知道单词中的字母数量
• 消除字典中所有字母数不正确的单词。
• 选择字典剩余子集中出现最多单词的尚未猜到的字母。
• 如果这封信出现，我们就知道它的位置。
• 如果这个字母没有出现，我们知道它不会出现在单词中。
• 消除字典子集中不完全符合这个正确模式的所有单词，然后重复。
• 如果有 2 个（或更多）字母出现的频率相同，则算法可能会对位置进行更深入的分析，以确定首选哪个字母（如果这是合理的？）

在每个阶段，我们都在猜测出现在剩余可能单词中的最大数量的字母（之前没有猜到）。

喜欢这个算法有一些动机——我们总是极不可能失去生命。

但是，令我震惊的是，这不一定是最好的解决方案：如果我们试图猜测这个词（在一定数量的生命中），并不一定总是出现频率最高的字母是最有用的字母以区分剩余的可用单词。

不过，我不确定，因为尽可能避免失去生命似乎是合适的。最优策略是否会允许我们牺牲生命以获得更好的获胜机会？

问题：这种贪心算法是否等同于最佳获胜机会算法？你能证明吗？

一个示例字典+游戏将是展示反证的理想选择。

你知道谁知道你想参加聚会的 n 个人中的谁。假设“知道”是对称的：如果我认识你，你就认识我。你提出了进一步的要求，你希望每个人至少有 5 个新人在聚会上见面，而且，没有人会感到太孤立，每个人应该已经认识至少 5 个聚会上的人。您的原始列表可能不满足这两个额外的条件，因此您可能需要从邀请列表中删除一些人（或者您可能根本无法在这些限制下举办派对）。从您可以邀请的 n 个人中找出一个最大可能的子集，并满足其他两个要求。对于基本问题，找到一个 O(n^3) 算法并解释其顺序和逻辑。

我要求的不是答案，而是从哪里开始的指导。

输入是一个实数序列 x1, x2, ..., x2n。我们想将这些数字配对成 n 对。对于第 i 个对 (i = 1, 2, ..., n)，让 Si 表示该对中的数字之和。（例如，如果将 x(2i−1) 和 x2i 作为第 i 对配对，则 Si = x(2i−1) + x2i）。我们希望将这些数字配对，以使 Maxi[Si] 最小化。设计一个贪心算法来解决这个问题。

这就是问题所在; 我的解决方案是简单地对数字进行排序并配对倒数第一的元素和加一/减一索引并重复。该算法尝试对每一对进行优化，从而使其变得贪婪。我只是想知道是否有一个线性时间算法可以做到这一点？

PS：这不是作业，但我知道这看起来很像。

这是流行的 El Goog 问题的变体。

考虑以下调度问题：有 n 个作业，i = 1..n。有 1 台超级计算机和无限的 PC。每个作业都需要先经过超级计算机的预处理，然后再在 PC 上进行处理。超级计算机上作业 i 所需的时间为 si，i = 1..n。对于 PC，它是 pi，i = 1..n。PC 可以并行工作，但超级计算机一次只能完成一项工作。创建一个时间表 S，超级计算机将根据该时间表处理这些作业。计划 S 中的完成时间 Ti(S) 由 PC 上作业完成的时钟时间给出。我们想找到一个最小化 Maxi[Ti(s)] 的时间表（可以理解为：我们需要找到一个最小化最高完成时间的时间表）. 提出了以下贪心算法： 在 PC 上按处理时间的递减顺序排列作业。该算法的复杂度为 O(nlogn)。要么证明这个算法产生了一个最优解，要么提供一个反例来证明它没有。

我的解决方案（不确定这是否正确）：我认为我们如何订购工作并不重要。最高完成时间仍然相同。考虑这个在 PC 上处理作业列表的时间示例：<5、7、17、8、10>。这将产生 <5, 12, 29, 37, 47> 的完成时间。根据算法，我们将列表排序为 <17, 10, 8, 7, 5> 并将产生 <17, 27, 35, 42, 47> 的完成时间。因此，虽然从技术上讲，贪心算法确实给出了最佳排序，但它需要 nlogn 时间来做到这一点，而简单地遍历作业列表会给我们同样的结果。

如果有人认为贪心算法会更好，或者我的方法有缺陷，我会很感激你的想法。谢谢！

更新：我想我可能有答案。超级计算机花费的时间无关紧要。这里的关键是 PC并行运行。从 pi = <5, 7, 17, 8, 10> 的初始示例中，让我们添加 si = <8, 5, 1, 12, 9>。现在，在默认的未排序顺序中，我们的处理时间为 <13, 20, (8 + 5 + 1 + 17 = )31, 34, 45>。所以 45 是完成的时间。假设 pi 的排序顺序是递减的。输出为：<18、20、30、34、40>。[排序输入：pi = <17, 10, 8, 7, 5>, si = <1, 9, 12, 5, 8>]。

这里有一个例子可以说明一切：si = <17, 10>, pi = <10, 17>。未排序情况下的输出（也恰好按 si 的降序排序）将是 <27, 44>。根据 pi 排序，输入为：si = <10, 17>, pi = <17, 10>。输出为 <27, 37>。由于 PC 并行运行，因此您希望最后发送最短的作业。

整数序列 X=x1,x2...,xn 定义为 ZIG-ZAG 如果：

xi < xi+1 如果 xi 是奇数
xi > xi+1 如果 xi 是偶数

我需要一个贪心算法来找到给定序列内最大 ZIG-ZAG 子序列的维数

编辑：有一个例子：
Y = (3, 4, 8, 5, 6, 2)
对于 3、8、5、6、2 或 4、8、5、6、2，输出应该是 5

问题陈述

c是给定的n整数数组；问题是找到一个递增的n整数数组，以a (a[i] <= a[i+1])使这个总和最小化：

最优a存在仅由出现的整数构成，c因此我们可以使用 DP in 解决它O(n^2)：

但是应该有一个更快的解决方案，可能O(n lg n)。