问题标签 [greedy]

我曾经在我的桌面上采用以下格式的任意文件集：

屏幕截图 2011-11-08 在 8.10.23 AM.png

屏幕截图 2011-11-08 在 8.08.57 AM.png

在它们上运行 Perl 脚本并将它们重命名为

SS-2011-11-08 上午 8.10.23.png

SS-2011-11-08 在 8.08.57 AM.png

这停止工作并且没有重命名发生。现在我必须更改它，我希望它更改为：

ss-2011.11.08.at.8.10.23.AM.png

ss-2011.11.08.at.8.08.57.AM.png

• 将“Screen Shot”替换为“ss”
• 全部替换-为.
• 将所有空格替换为.

我知道这与贪婪有关，但我没有写这个，无论我做了多少摆弄，我似乎都无法让它发挥作用。在我的生活中，我已经使用了几个小时的 perl。我想我可以用几行代码在 php 中做到这一点，但我想学习如何将它保存在 perl 中，因为能够调试总是好的。我查看了 regs 格式规则，但它们不适用。要么 Mac OS X Lion 出现问题，要么 Snow Leopard 允许不应该发生的事情发生。

谢谢你们！

这是我到目前为止所拥有的：

无论我做什么，我的正则表达式都匹配该行中的最后一组字母字符。我希望它只匹配第一次出现。

我尝试过使用非贪婪运算符，但它顽固地匹配最右边的字母字符集，在这种情况下，$1 的值是“Trig”，这不是我想要的。我希望 1 美元是“02.04.07.06 Geerite”。

代码

资源

02.04.07.06 Geerite Cu8S5 R 3m、R 3m 或 R 32 Trig

输出

NT2 32 三角 | |

所以换句话说，我想要这个输出：

NT2 02.04.07.06 Geerite | |

问题是如何使用以下信息用贪心算法跟踪背包问题？

如果有人能帮助我理解这一点或指出我正确的方向，我将不胜感激。

The following gives a practical example:

Let's say for m = 4:

I have to find a set of indexes e.g. A = { 1, 2, 3 } so that U (Seti) includes Set5, where i is part of A. The cardinal of A must be minimal.

在我开始之前，是的，这是一个家庭作业。如果我在过去 14 小时内没有尽我所能解决这个问题并且一无所获，我就不会在这里发帖。

问题如下：我想检查是否可以在 O(V) 时间内从连接的无向图中删除一条边而不断开它，而不仅仅是线性的。

到目前为止我所达到的：

可以在不断开图形的情况下删除循环边缘，因此我只需检查图形是否有循环。我有两种方法可以使用，一种是 DFS，然后检查我是否有后边缘；另一种是通过计算 Vs 和 Es 并检查是否 |E| = |V| - 1，如果这是真的，那么图是一棵树，没有节点我们可以在不断开连接的情况下删除它。

前面的两种方法都解决了这个问题，但都需要 O(|E|+|V|)，而且书上说有一种更快的方法（这可能是一种贪婪的方法）。

请问我可以得到任何提示吗？

编辑：更具体地说，这是我的问题；给定一个连通图 G=(V,E)，我可以删除 E 中的一些边 e 并且结果图仍然是连通的吗？

假设有N组人和M张桌子。我们知道每个组的大小和每个表的容量。我们如何将人与桌子匹配，以使同一组的两个人不会坐在同一张桌子上？

贪婪的方法是否适用于这个问题？（贪婪方法的工作原理如下：为每张桌子尝试“填充”来自不同群体的人）。

一个数据文件包含一个 8 位字符序列，因此所有 256 个字符大致相同：最大字符频率小于最小字符频率的两倍。证明这种情况下的霍夫曼编码并不比使用普通的 8 位定长编码更有效。

问题在这里：http ://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2384

我设法使用贪婪的方法解决了这个问题。我将早上的路线按降序排列，晚上的路线按升序排列，然后我将早上路线的最大值与晚上路线的最小值放在一起。该解决方案被接受。我试图证明这个问题具有贪心选择属性，即贪心选择是最优解的一部分。有人可以帮忙证明一下吗。我做这个证明只是为了练习

我花了几个小时试图理解这个问题的答案。我只是不明白。有人可以给我一些基于答案解决这个问题的算法的伪代码（最好是类似于Java的伪代码）吗？这将帮助我理解答案的意思。

问题和答案：

与其全部输入，不如在此 PDF 中更好地设置样式。问题是 pdf 中的第一个问题，练习 16.1-4

http://mitpress.mit.edu/algorithms/solutions/chap16-solutions.pdf

（澄清一下，他不是功课，我正在做书本，想了解这个问题。链接是问题的解决方案，但我不明白。我不明白它说的是什么意思“要做到这一点，请按照事件时间的顺序浏览一组由活动开始和活动结束组成的事件......”以及其余的解释。这就是为什么，如果有人理解它，我希望他们能展示我是这个解释的伪代码。我可以通过这种方式阅读和理解它。比如函数的参数是什么，函数内部发生了什么，活动如何迭代，它们如何在两个繁忙和空闲的报告厅列表等）谢谢

在一个类似的问题中，我询问了如何使用权重分配整数。我很好奇如果对每个分布“桶”施加最小值，人们将如何解决这个问题。通过施加最小值，这似乎是一个更加困难的问题。这是我的贪婪尝试，但不起作用：

目前，这些值被分配为 [7, 5, 4]，即 16，比我们必须分配的多 6 个。输出应该是 [1, 5, 4] 因为这满足所有列的最低要求。随着我们必须分配的价值的增长，分布应该越来越接近正确的加权分布。例如，通过分配 1000，算法正确地将值分配为 [714, 143, 143]。

作为旁注，我的目的是在几列之间分配可用空间（宽度）。所有列都具有“通过”并显示至少部分数据所需的最小大小，并且随着可用空间的增长，某些列更需要空间。我提到这是该算法在现实生活中的一种用途，但我不希望这是对 GUI 设计的讨论。

这个问题有哪些解决方案？越简单越好。