问题标签 [greedy]

我正在尝试编写一个正则表达式，它将完整路径文件名转换为给定文件类型的短文件名，减去文件扩展名。

例如，我试图从字符串中获取 .bar 文件的名称，使用

根据 Python re docs，*?是不贪婪的版本*，所以我期待得到

返回match.group(1)但我得到了

关于贪婪，我在这里错过了什么？

我需要知道如何使用 C# 在纸牌游戏中实现贪心算法。游戏是回合制游戏。当AI应该发一些牌时，必须基于已经在桌上的其他牌的最新状态。有没有人对此有解决方案，或者可能是我开始的参考？提前致谢！

现在我只完成了洗牌的代码：

实际上，我已经对这个问题有了部分答案，但我想知道是否可以将这一小段贪婪的代码推广到更接近最佳解决方案的东西。

我是如何遇到这个问题的（与问题本身无关，但可能很有趣）：

我收到了大量的对象（这是一组堤坝的轮廓，每个堤坝沿其长度保持或多或少相同的形状），我可以根据属性（堤坝的名称）对它们进行分组。我的程序输出到一个外部程序，我们必须手动调用它（不要问我为什么），它不能从失败中恢复（一个错误会停止整个批处理）。

在我使用它的应用程序中，对垃圾箱的数量和垃圾箱的最大尺寸没有硬性要求，我尝试做的是

• 保持低组的数量（多次调用程序。）
• 保持较小的集合（如果批次失败，减少损坏）
• 把相似的东西放在一起（一个小组的失败可能是整个小组的失败）。

我没有太多时间，所以我写了一个小贪心函数，将集合组合在一起。

一位同事建议我可以在数据中添加一些噪音来探索我找到的近似解的邻域，我们想知道找到的解离最优还有多远。

并不是说它与原始任务相关，它不需要真正的最佳解决方案，但我想我会与社区分享这个问题，看看它会产生什么评论。

如何对图应用 Dijkstra 算法以找到 MST，使得生成的树必须在两个给定顶点之间有一条边？（例如：MST 必须包含 X 和 Y 之间的边）

谢谢

我在理解 cilk 中多线程编程中贪婪调度的完整步骤和不完整步骤时遇到问题。

这是供参考的power-point演示文稿。

Cilk ++ 多线程编程

我理解的问题来自幻灯片# 32 - 37。

有人可以请特别解释一下如何

感谢您的时间和帮助

最近我一直在研究一些贪心算法问题。我对局部最优感到困惑。如您所知，贪心算法由局部最优选择组成。但是结合局部最优决策并不一定意味着全局最优，对吧？

以找零为例：用最少的硬币来凑 15 美分，如果我们有 10 美分、5 美分和 1 美分的硬币，那么你可以用一个 10 美分和一个 5 美分来实现。但是如果我们添加一个 12¢ 的硬币，贪心算法就会失败，因为 (1×12¢ + 3×1¢) 使用的硬币比 (1×10¢ + 1×5¢) 多。

考虑一些经典的贪心算法，例如 Huffman、Dijkstra。在我看来，这些算法是成功的，因为它们没有退化的情况，这意味着局部最优步骤的组合总是等于全局最优。我理解对了吗？

如果我的理解是正确的，是否有检查贪心算法是否最优的通用方法？

我在网站的其他地方发现了一些关于贪心算法的讨论。但是，这个问题并没有涉及太多细节。

我有这样的表达：

我想匹配[d .-][]第一对括号内可能包含任何字符（字母、数字、标点符号等）的第四个元素，但第二对括号仍然为空。其他元素，例如，[a][1]可以包含任何字符，但它们在第二对括号内确实有一个数字。

我试过这个：

但它太贪心了。

任何帮助，将不胜感激。

我有一些关于算法的一般性问题，当你有一些问题并且你想编写一些算法时，你如何解决这个问题，你如何决定使用哪种算法使用贪婪算法或动态规划？提前致谢

我实际上正在练习贪婪算法，并且 topcoder 有问题..所以需要一些帮助....

问题是关于健壮的计算机系统.. http://www.topcoder.com/stat?c=problem_statement&pm=2235&rd=5070

我不明白什么是MFC。（最大失败次数）？

如果有人可以通过简单的示例阐明 MFC 的解释，那将是有帮助的！

谢谢..

如果您没有帐户，并且无法访问链接，那么问题如下：

在强大的计算机系统中，最重要的部分之一是冷却。如果没有适当的冷却，处理器的温度可能会高达 400 摄氏度以上。系统的可靠性可以通过确定有多少风扇可以在不危及系统处理器的情况下发生故障来衡量。可以为每个风扇分配一个值，指示它有多少容量来冷却系统，我们可以定义最小冷却能力，风扇容量的总和必须超过该值才能正确冷却系统。我们将故障集定义为一组不需要冷却系统的风扇。换句话说，如果故障集中的风扇发生故障，系统仍然可以由剩余的风扇适当冷却。故障集的计数是该集中的风扇数。

为了衡量可靠性，我们将定义两个值，最大故障集 (MFS) 和最大故障计数 (MFC)。MFS 是具有最大可能数量的风扇故障集。一组风扇可能有多个 MFS（见下文）。当且仅当不存在具有更高计数的故障集时，故障集才是 MFS。MFC 是最大值，因此所有计数 <= MFC 的风扇集都是故障集。换言之，任何 MFC 或以下尺寸的风扇都可能发生故障，系统仍将由剩余的风扇适当冷却。

考虑具有容量 1、2、3 和冷却要求 2 的风扇组。存在两个计数为 2 的 MFS：风扇 1 和 3，或风扇 1 和 2。但是，MFC 不是 2，因为风扇 2 和3 不是故障集（风扇 1 无法自行正确冷却系统）。因此，MFC 为 1，因为如果任何一个风扇发生故障，系统仍然可以冷却。

您将获得一个 int[] 容量，它指定每个风扇提供多少冷却单位，以及一个 int minCooling，它指定冷却系统所需的最小冷却单位。您的方法应该返回一个 int[]，其中第一个值应该是最大故障集 (MFS) 中的风扇数，第二个值应该是最大故障计数 (MFC)。

什么是 PHP 中的贪婪令牌解析？我正在阅读一个 PHP 编码指南，它说以下内容......

“除非您需要解析变量，否则请始终使用单引号字符串，并且在确实需要解析变量的情况下，请使用大括号来防止贪婪的令牌解析。如果字符串包含单引号，您也可以使用双引号字符串，因此您没有使用转义字符。”

这是在我的变量周围使用花括号某种安全过程来排除黑客攻击吗？（例如 {$var}）是贪婪的令牌解析黑客可以使用的某种攻击，例如 SQL 注入或 XSS（跨站点脚本