问题标签 [greedy]

Kruskal 最小生成树算法的反面是否适用？我的意思是，每一步都选择最大重量（边缘）？

找到最大生成树的任何其他想法？

好的，我有一个问题。我有一套“A”瓶大小不一的瓶子，都装满了水。然后我有另一组不同大小的瓶子“B”，都是空的。

我想将水从 A 转移到 B，知道每组的总容量是相同的。（即：A 组的水量与 B 组相同）。

这本身当然是微不足道的，只需将 B 中的第一瓶，倒入 A 中的第一瓶，直到这瓶装满。然后如果 B 的瓶子里还有水，继续用 A 的第二个瓶子，以此类推。

但是，我想尽量减少倾倒的总数（从一个瓶子倒进另一个瓶子的动作，每个动作都算 1，与它涉及的水量无关）

我想找到一种贪心算法来做到这一点，或者如果不可能，至少是一种有效的算法。但是，效率次于算法的正确性（我不想要次优的解决方案）。

当然，这个问题只是计算机程序中管理个人开支的实际问题的隐喻。

有正则表达式〜像这样：

如果我找到一个 url，我想捕获一个……找到了东西，但我没有得到链接（捕获总是空的）。现在，如果我像这样删除最后的问号

这只会匹配最后有链接的东西......现在是凌晨 2.40......我不知道......

- 编辑 -

样本输入：

blablabla asd 1234t535 <a href="http://google.com" target="_blank">

预期输出：

match 0:

我只想要“http://google.com”或“”

我正在尝试匹配来自 HTML 源的特定跨度标签。

标记的语言属性和内部 HTML 用作返回新字符串的函数的参数。

我想用被调用函数的结果替换旧的标签、属性和内容。

主题将是这样的：

为了提取 lang 属性的值和内容，我使用以下表达式对这些值进行分组：

由于正则表达式往往是贪婪的，这个表达式匹配完整的主题，而不仅仅是一个跨度标签及其内容。

我如何设法只匹配一个跨度标签？

我有一个像 "===text=== 和 ===text===" 这样的输入字符串，我想用相应的 html 标记替换 wiki 语法。

输入：

理想的输出：

但是使用以下代码，我得到了这个输出：

我知道问题是我的正则表达式匹配贪婪。但是如何让他们不贪心。

谢谢你和亲切的问候。丹尼

支配集 (DS) := 给定一个无向图 G = (V;E)，如果对于 V 中的每个顶点，S 中都有一个与 v 相邻的顶点，则一组顶点 SV 是支配集。整个顶点集V 是任何图中的平凡支配集。

找到一棵树的最小尺寸支配集。

我有一个数字金字塔。每个数字代表关联的点数。我需要使用贪心算法来找到从金字塔顶部到底部的成本最低的路径。我读过关于不知情和知情的搜索算法，但我仍然不知道该选择什么。你觉得什么最适合这类问题？贪婪的最佳优先搜索/A* 搜索还是其他？这是一个如此简单的问题，但我并没有使用所有这些算法来知道什么是最佳选择。正如我所说，它必须是一个贪心算法。

我想对“a”的零到“m”个连续出现或“b”的零到“n”个连续出现的替代进行贪婪匹配。如果我做

它不起作用，因为当我有 'b' 序列时，它将与 'a{,m}' 匹配，而替代的 'b{,n}' 将不会被查看，也不会是贪婪匹配.

我有以下问题：给定一组 N 个整数，将它们分成两个几乎相等的分区，使得较大分区的总和最小。这听起来几乎像经典的分区问题，但有一个例外：偶数可以被 2 整除，并且每一半都可以放在一个单独的分区中。

例如：N = 4 数字：20 5 3 1

结果是：15

解释：第一个数字将被二除，每半放在两个分区之一 => 第一个分区 = 10，第二个分区 = 10。第二个数字将添加到第一个分区 => 第一个分区 = 15。最后两个数字将添加到第二个分区 => 第二个分区 = 14

=> 更大分区的总和（分区一）= 15。

我的想法是对奇数进行递减排序并使用贪心算法开始添加它们，始终保持两个分区之和之间的差异尽可能最佳。在完成奇数之后，剩下的就是取偶数，看看是否将它们完全添加到一个分区中，是否比将它们除以 2 并将每一半添加到这两个分区中的一个分区中更好。

同样对于以下数据集，算法将提供正确答案：N = 2 数字：16 15

=> 将取 15，将其添加到第一个分区，然后取 16，看到将其除以 2 不是最佳的，因此它将添加到第二个分区。

=> 答案将是 16。

如果您能给我提供一组数据，算法无法提供最佳答案，我很感兴趣，如果您能提出任何改进建议，我也将不胜感激。

谢谢！:)

我正在为我编写的以下贪心算法而苦苦挣扎；我知道我的算法不完整，但我真的不知道如何改进它。：

这就是问题的表述：要销售其各种产品，公司需要“n”个许可证。由于某些法律，它每月不能获得超过一个许可证。此外，许可证的成本每月都在增加。事实上，虽然目前每个许可证的成本为 100.00 美元，但许可证 j (1 ≤ j ≤ n) 的成本每月增加 rj> 1 倍（rj 是参数）。换句话说，例如，在前四个月购买许可证的费用为 100r4，而在第五个月购买许可证的费用为 100(r3)^5 美元。最后，我们假设 ri 与 rj 不同，因为 i 与 j 不同。那么问题是，对于给定的一组 rj (1 ≤ j ≤ n)，以什么顺序购买“n”个许可证以最小化总拥有成本。1. 使用贪心方法开发一个多项式算法来解决这个问题。在最坏的情况下分析你的算法。2. 证明你的算法能很好地返回最优解。3. 在以下实例中说明您的算法：n = 3, r1 = 3, r2 = 4, r3 = 2。

谢谢