问题标签 [greedy]

使用 JAVA 在给定字符串中捕获以下组的正则表达式是什么：

约束条件是第一个单词也可以包含逗号。我有以下正则表达式：

但我基本上只想匹配最后 3 个逗号。

我的问题是，我们得到了一份活动列表以及开始和结束时间，然后我们必须找出我们可以做的最大活动。这个问题很常见，我已经应用了一种贪婪的方法，但是我的代码中出现了运行时分段错误，所以我将它发布在下面。

请帮助！提前谢谢！！

以下是我们 CS 算法讲师的 Kruskal 最小生成树算法的伪代码。我想知道 MST 算法是否是不确定的。给定具有相同权重的两条边，如果在添加到 T 时没有一条边形成循环，算法将如何在它们之间做出决定。当然，如果它是随机的，那么我们无法确定将哪些确切边添加到 T 的结果？

谢谢！

给定一个无向加权图 G = (V,E)。每个顶点代表一个城市，连接 a 和 b 的边的权重是完成在城市 a 和城市 b 之间建立高速路线所需的年数。描述一种算法，该算法将找到一个人可以在图中任意两个城市之间旅行的最少年数。路线是同时建立的，所以如果我们有三个城市 a、b 和 c 以及 a 和 b 之间的一条边，权重为 1，b 和 c 之间的另一条边，权重为 2，那么输出应该是 2。

问题

假设我们有一组N个实数 A = {x_1, x_2, ..., x_N}。

目标是将此集合划分为A_1、A_2、...、A_L子集，并限制sum( A_i ) <= T并最小化此项：

成本 := sum( abs( sum(A_i) - T ) )

其中sum(A_i)表示 A_i 中数字的总和，T是给定的阈值。

我正在寻找一种非进化最优算法。

更新： x_i是实数并且不大于T ( 0 < x_i <= T )。

更新 2：固定成本函数。

不错的尝试，贪心算法！

一个简单的想法是使用贪婪方法来解决问题。这是一个伪代码：

问题是这个解决方案不是最优的。例如，在某些情况下，最好不要将两个最大的数x1和x2放在第一个子集A_1中，即使它们不超过T，因为没有其他 *x_i* 可用于添加到该集合并使它的总和更接近T。另一方面，如果我们将x1和x2放在不同的集合中，则可以找到更好的解决方案（成本值较小的解决方案）。

可能的解决方案

我曾想过使用回溯算法，它也可以找到最佳解决方案，但我猜它在这个问题中的复杂性会很高。

我已经阅读了维基百科上的一些文章，例如装箱问题（NP-hard [sighs...]）和切割库存问题，显然我的问题与这个标准问题非常相似，但我不确定哪一个符合我的情况。

我有一串长度1 <= |S| <= 100和K (1 <= K <= 10)

此字符串包含digits < K和问号。我想用 替换这些问号digits < K，没有两个相邻的数字相等。字符串是圆形的，所以它不能是这样的：1?1或11?.

结果字符串必须是按字典顺序最小的字符串。

示例输入和输出

我尝试了一种贪婪的方法，但对于一些未知的测试用例它失败了。我认为它需要一种 dp 方法，但无法弄清楚状态，并且纯递归代码无法及时适应。

对 dp 方法有什么帮助，或者无法满足贪婪的棘手测试用例？

谢谢，

我有一个简单的算法问题。如果你能帮助我，我将不胜感激。

我们有一些二维点。正权重与它们相关联（附有示例问题）。我们想要选择它们的一个子集来最大化权重，并且两个选定的点都不相互重叠（例如，在附件中，我们不能同时选择 A 和 C，因为它们在同一行中，并且以相同的方式我们不能同时选择 A 和 B，因为它们在同一列中。）如果有任何贪婪（或动态）方法我可以使用。我知道非重叠区间选择算法，但我不能在这里使用它，因为我的问题是二维的。

任何参考或注释表示赞赏。

问候

附件：问题的简单示例：

我看到人们倾向于 DP 方法而不是贪婪方法，因为它可以解决优化问题。大家觉得哪一个更可取呢？我需要收集论据以支持与我的伙伴争论的更好技术。哈哈。好的，DP用于解决具有最优子结构和最优性原理的问题。但是DP比贪婪的方法更好吗？

大多数时候，令人困惑的事实是是采用详尽的搜索（动态编程或回溯或蛮力）来解决问题还是采用贪婪的方法。

我不是在谈论使用贪心算法来确定可能的最佳解决方案，而是在谈论使用贪心算法来找到“解决方案”。我正在尝试获得一些标准方法来验证问题是否可以通过贪婪的方法解决。像最优子结构，动态规划的记忆。并且不涉及任何具体问题。

是否有任何归纳证明我可以确定贪婪方法是否总是能产生最佳解决方案？

给定一个可以建模为有根树的逻辑电路——叶子是主要输入，内部节点是门，根是电路的单个输出。每个门可以由高或低电源电压供电。由较低电源电压供电的门消耗较少的功率，但输出信号较弱。您希望在确保电路可靠的同时最大限度地降低功耗。为确保可靠性，不应让一个由低电源电压供电的门驱动另一个由低电源电压供电的门。所有栅极在连接到低电源电压时消耗 1 纳瓦，在连接到高电源电压时消耗 2 纳瓦。

设计一种有效的算法，将逻辑电路作为输入并为每个门选择电源电压，以最大限度地降低功耗，同时确保可靠运行。

在这个问题中，我认为，它可以通过使用贪婪或动态来解决。但是我很困惑从哪里开始思考这个问题。请帮忙。