标签: greedy

在间隔调度中，算法是选择最早的完成时间。但是在间隔着色中，前者无效。是否有示例或解释说明为什么最早的完成时间不能用于间隔着色？

间隔着色问题是：给定？一组“间隔”，我们要“给所有颜色上色”吗？间隔？这样？间隔？给吗？该？相同？颜色？不相交？和“目标”？是“尝试”为？最小化使用的颜色数。可以将其视为间隔分区问题（如果更合理）

我指的是间隔安排问题：如果您去主题公园并且有很多演出，那么每个节目的开始和结束时间就是一个间隔，您就是资源。您想参加尽可能多的演出。

如何使用正则表达式在 Stata 中实现非贪婪匹配？或者Stata有这个能力吗？

我想提取主题标签“#”和句点“.”之间出现的所有文本。

示例代码：

clear
set obs 3
generate var1="anything#aaabbbccc.dddeee.fff" in 1
replace var1="anything#aaabbbccc.dddeee" in 2
replace var1="anything#aaabbbccc." in 3
generate var2=regexs(1) if regexm(var1,"#(.*)\.")
list

但在 Stata (v.13.1) 中，我似乎无法使用非贪婪字符#(.*?)\.。因此，上面的代码给出了：

+--------------------------------------------------+
|                          var1               var2 |
|--------------------------------------------------|
| anything#aaabbbccc.dddeee.fff   aaabbbccc.dddeee |
|     anything#aaabbbccc.dddeee          aaabbbccc |
|           anything#aaabbbccc.          aaabbbccc |
+--------------------------------------------------+

但我想要的是这样的：

+--------------------------------------------------+
|                          var1               var2 |
|--------------------------------------------------|
| anything#aaabbbccc.dddeee.fff          aaabbbccc |
|     anything#aaabbbccc.dddeee          aaabbbccc |
|           anything#aaabbbccc.          aaabbbccc |
+--------------------------------------------------+

我正在构建一个语法ANTLR4,我收到了这个警告

TL4.g4:224:12: greedy block ()* contains wildcard; the non-greedy syntax ()*? may be preferred

这是它所指的代码行

block
    : ( statement | functionDecl )* (Return expression ';')?
    ;

警告意味着什么,我该如何纠正？

给定一个整数数组，找出大小为 k 的最小词法子序列。 EX: Array : [3,1,5,3,5,9,2] k =4 Expected Soultion : 1 3 5 2

我们有以下预处理器宏。它用于帮助Doxygen文档，因为Doxygen在使用C ++和某些模板typedef时遇到了麻烦：

#if defined(DOXYGEN_PROCESSING)
# define DOCUMENTED_TYPEDEF(x, y) class y : public x {};
#else
# define DOCUMENTED_TYPEDEF(x, y) typedef x y;
#endif

如果X是非模板或只有一个模板参数，则效果很好。但是，如果X是具有多个参数的模板：

DOCUMENTED_TYPEDEF(Foo<R,S>,Bar);

然后，由于将字符串拆分为Foo<R和S>,Bar（并且不会生成文档），将导致编译错误。

如何使预处理器宏贪婪？

给定树的根,其中每个边具有相关的成本.找到访问树的每个节点的最低成本.

我想到的一个递归解决方案是:

1. 当节点是叶返回0时的基本情况.
2. 对于节点的每个子节点c递归地计算成本.
3. 将所有这些成本加起来,并且从节点到子节点两次添加边缘成本两次(因为我们需要回溯).
4. 减去具有最大成本的孩子的边缘成本.("贪婪" - 我们不想从具有最大成本的孩子回溯).

这种方法是否正确？

有没有更好的方法来解决这个问题？

好吧,我们有贪婪的算法用于作业调度(调度最大作业数).我们可以使用不同的技术

1. 最短的工作
2. 最早的开始时间
3. 首先是最小冲突的工作
4. 最早的结束时间

我有前三个策略的反例,但我找不到第四个策略的反例.

这里是前三种方法的反例

最短的工作优先:

在这里,我们可以安排2个工作而不是短工作.

最早的开始时间:

在这里,我们可以安排6个较小的工作,而不是之前开始的工作

首先是最小冲突的工作:

在这里,我们可以安排4个冲突3,4,4,3而不是3个冲突最小的工作,即2,3,3

那么,最后一个最早结束时间的反例是什么,首先我找不到这个的反例.那么,它总能为每组数据提供最佳解决方案吗？

更新1:

我有一个执行程序来执行作业,我想执行最大数量的作业.

在我的代码中,我使用了贪婪的算法,以便使用最少的硬币数量.例如:我必须返回0.41美元,我可以使用的最小硬币数量是4:

1 - 0,25;
1 - 0.10;
1 - 0.05;
1 - 0.01;

有4种类型的硬币:0.25,0.10,0.05,0.01.

这是我的代码:

#include <stdio.h>
#include <cs50.h>

int main(void)
{
    printf("Enter the sum, that you want to return you:");
    float sum = GetFloat();
    float quaters = 0.25;
    float dime = 0.10;
    float nickel = 0.05;
    float penny = 0.01;
    int count_q = 0,count_d = 0,count_n = 0,count_p = 0;


    while(sum<0){
        printf("Incorrect, enter the positive float number");
        sum = GetFloat();
    }

    while(sum > 0){
        if(sum - quaters >=0){
            sum …

我想在haskell中实现3问题的最高产品的算法.这是问题陈述:

给定一个整数数组,找到可以从三个整数中得到的最高乘积.

例如,给定[1, 2, 3, 4],算法应该返回24.并给出[-10, -10, 5, 1, 6],3的最高产品将是600 = -10*-10*6.

我的尝试(第一次尝试没有否定):

sol2' a b c []     = a*b*c
sol2' a b c (x:xs) = sol2' a' b' c' xs
  where 
    a' = if (x > a) then x else a
    b' = if (x > a && a > b) then a else b
    c' = if (x > a && a > b && b …

我有一个使用贪婪算法解决汽车加油问题的小问题。

问题介绍

您将前往距离您家乡数英里的另一个城市。您的汽车在加满油箱的情况下最多可以行驶数英里，而您从加满油箱开始。沿途有加油站，距离 stop1 stop2 。. . ,stopN 从你的家乡城市。最少需要多少次补充？

输入：

950
400
4
200 375 550 750

输出：

2

到目前为止我尝试过的

def car_fueling(dist,miles,n,gas_stations):
  num_refill, curr_refill, last_refill = 0,0,0
  while curr_refill <= n:
    last_refill = curr_refill
    while (curr_refill <= n-1) & (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles):
        curr_refill += 1
    if curr_refill == last_refill:  
      return -1
    if curr_refill <= n:
      num_refill += 1
  return num_refill

我面临的问题是什么

在声明中

while (curr_refill <= n-1) & (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles)

我收到错误IndexError: …