标签: greedy

对于在分隔符(例如<和>)之间匹配文本的常见问题,有两种常见的模式:

• 使用形式中的贪婪*或+量词START [^END]* END,例如<[^>]*>,或
• 使用形式中的惰性*?或+?量词START .*? END,例如<.*?>.

是否有一个特别的理由支持一个而不是另一个？

我正在阅读关于"贪婪"算法的教程,但我很难发现它们解决了真正的"顶级编码器"问题.

如果我知道某个问题可以通过"贪婪"算法解决,那么对解决方案进行编码就非常容易了.但是,如果我没有被告知这个问题是"贪婪的"我无法发现它.

使用"贪婪"算法解决问题的常见属性和模式是什么？我可以将它们减少到已知的"贪婪"问题之一(例如MST)吗？

在这篇文章中,它将Dijkstras描述为一种贪婪的算法,而在这里和这里它被证明与动态编程算法有联系.

那是哪一个呢？

例如:数组:4,3,0,1,5 {假设所有数字> = 0.数组中的每个元素也对应一个数字.即数组中的每个元素都在0到9之间.}

在上面的数组中,最大的数字是:5430 {使用数组中的数字5,4,3和0}

我的方法:

对于3的可分性,我们需要数字的总和可以被3整除.所以,

1. 步骤1:从阵列中删除所有零.
2. 第2步:这些零将在最后出现.{因为他们不影响总和,我们必须找到最大的数字}
3. 步骤3:找到数组元素的子集(不包括零),使得位数为MAXIMUM,并且数字之和为MAXIMUM,总和可以被3整除.
4. 步骤4:所需数字由上面找到的数字按降序排列.

因此,主要步骤是STEP-3,即如何找到子集,使其包含MAXIMUM可能数量的元素,使得它们的和为MAX,并且可以被3整除.

我在想,也许Step-3可以通过GREEDY CHOICE来完成所有元素并继续删除集合中的最小元素,直到总和可以被3整除.

但我不相信这个贪婪的选择会起作用.

请告诉我的方法是否正确.如果是,那么请建议如何做第3步？

此外,请建议任何其他可能/有效的算法.

在(正)整数的非递减序列中,当可以去除两个元素时 .从这个序列中最多可以删除多少对？

所以我想到了以下解决方案:

• 我采用给定的顺序并分成两部分(第一和第二).
• 分别为它们分配迭代器 - it_first:= 0和it_second:= 0.count:= 0
• 当it_second!= second.length
  • if 2*first [it_first] <= second [it_second]
    • count ++,it_first ++,it_second ++
  • 其他
    • it_second ++
• 伯爵就是答案

例:

count:= 0

[1,5,8,10,12,13,15,24] - > 第一名:= [1,5,8,10],第二名:= [12,13,15,24]

1. 2*1？<12 - > true,count ++,it_first ++和it_second ++

2. 2*5？<13 - > true,count ++,it_first ++和it_second ++

3. 2*8？<15 - > false,it_second ++

4. 8？<24 - > true,count ++ it_second到达最后一个元素 - END.

5. count == 3

线性复杂度(最坏的情况是没有这样的元素被删除.n/2个元素与n/2个元素相比).所以我缺少的部分是算法的"正确性" - 我已经阅读了贪婪算法证明 - 但主要是树木,我找不到类比.任何帮助,将不胜感激.谢谢!

编辑: 正确性我的意思是:*它的工作原理*它不能更快​​地完成(在logn或常量)

我想放一些图形,但由于声誉点<10 - 我不能. …

贪心算法有什么用？一个真实的例子？

这是一个基于俄罗斯方块的谜题.在这个谜题中,我们将获得接下来将从顶部落下的n个片段的序列.我们的工作是在GameOver之前最大化得分.一般的俄罗斯方块没有多项式时间算法,但在这个难题中只允许I(直)四联体.虽然它不允许旋转它们.

所以这里是约束:

• 该板是W×H矩形
• 我们给出了下n个四联骨牌的序列
• 只允许我使用tetromino(水平或垂直)
• 不允许旋转
• 当行填满时,行会被清除
• 董事会最初是空的
• 每行清除1分.
• 当tetrominoes叠加到比赛场地的顶部时,游戏结束了.

找到可以获得的最高分数.

例:

8 x 6板.接下来的7个tetrominoes是[——,|,|,——,|,——,|]其中'——'表示水平我四氨基和|表示垂直我四氨基.

在这种情况下,最大可能得分是3使用以下策略('.'代表空板,'#'代表四氨基片的一部分).

Initially:
........
........
........
........
........
........
1st move:
........
........
........
........
........
####....
2nd Move:
........
........
.......#
.......#
.......#
####...#
3rd Move:
........
........
......##
......##
......##
####..##
4th Move:
........
........
......##
......##
####..##
####..##
5th Move:
........
........
.....###
.....###
####.###
####.###
6th Move:
........
........
.....### …

好的,我有一个问题.我有一套各种尺寸的瓶装"A",里面装满了水.然后我又拿了另一套各种尺寸的瓶子"B",都是空的.

我想将水从A转移到B,知道每组的总容量是相同的.(即:组A含有与组B相同的水量).

这当然是微不足道的,只需拿B中的第一个瓶子,倒入A中的第一个瓶子直到它满了.然后,如果B中的瓶子中还有水,请继续使用A中的第二个瓶子等.

但是,我想尽量减少浇注总量(从瓶子倒入另一个瓶子的动作,每个动作计数1,与其涉及的水量无关)

我想找到一个贪婪的算法来做到这一点,或者如果不可能,至少是一个有效的算法.然而,效率是算法正确性的次要因素(我不想要一个次优的解决方案).

当然,这个问题只是计算机程序中管理个人开支的真正问题的隐喻.

我认为默认情况下我的正则表达式会展示我想要的贪婪行为,但它不在以下代码中:

 Regex keywords = new Regex(@"in|int|into|internal|interface");
 var targets = keywords.ToString().Split('|');
 foreach (string t in targets)
    {
    Match match = keywords.Match(t);
    Console.WriteLine("Matched {0,-9} with {1}", t, match.Value);
    }

输出:

Matched in        with in
Matched int       with in
Matched into      with in
Matched internal  with in
Matched interface with in

现在我意识到,如果我只是按照长度降序对关键字进行排序,我可以让它为这个小例子工作

• 我想知道为什么这不能按预期工作,并且
• 我正在处理的实际项目在正则表达式中有更多的单词,并且按字母顺序保留它们非常重要.

所以我的问题是:为什么这是懒惰的,我该如何解决？

我有一个算法的问题.

给出n个盒子,每个盒子具有固定的重量和强度(均以kg给出).Box的力量告诉我们它能承受的最大重量是多少.我们必须形成最高堆的给定盒子(每个盒子具有相同的高度).您应该提出一种始终给出最优解的算法,这是k盒的最长序列(k <= n).

嗯,这是我已经想到的解决方案:

1. 首先,我们按重量对所有箱子进行分类(最重的是在底部)并形成一堆.
2. 其次,我们按强度排序(最强的是在底部).
3. 然后,对于每个盒子,从底部开始,我们尝试将其拉到底部,只要它的强度能够实现.
4. 最后,我们必须弄清楚必须从顶部移除多少箱子,这导致下面的某些箱子承载的重量超过他们的重量.

看起来这个算法工作得很好,但我不确定它是否总是给出最优解 - 可能它没有.我一直在想动态解决方案,类似于背包问题的解决方案,但我不确定它是否可以通过这种方式解决.对于我的问题,似乎没有最佳的子结构.

预先感谢您的任何帮助.:)