标签: greedy

最近,我在测试此问题:给定一组点米(全部在x轴)和一组 Ñ与端点[线的L,R ](再次在x轴),找到的最小子集n使得所有点都被一条线覆盖.证明您的解决方案始终找到最小子集.

我为它写的算法是这样的结果:(说行存储为数组,左端点位于0位,右端位于位置1)

algorithm coverPoints(set[] m, set[][] n):
    chosenLines = []
    while m is not empty:
        minX = min(m)
        bestLine = n[0]
        for i=1 to length of n:
            if n[i][0] <= minX and n[i][1] > bestLine[1] then
                bestLine = n[i]
        add bestLine to chosenLines
        for i=0 to length of m:
            if m[i] <= bestLine[1] then delete m[i] from m
    return chosenLines

我只是不确定这总是找到最小的解决方案.这是一个简单的贪婪算法,所以我的直觉告诉我它不会,但我的一个比我好得多的朋友说,对于这个问题,像这样的贪婪算法总能找到最小的解决方案.为了证明我的总是找到最小的解决方案我做了一个非常手的波浪证明矛盾,我做了一个假设,可能根本不是真的.我完全忘记了我的所作所为.

如果这不是一个最小的解决方案,有没有办法在比O(n!)时间更少的时间内完成它？

谢谢

我在高速公路上有一系列n服务站D[],这D[i]是车站i到高速公路起点的距离.

我还有一系列成本C[],这C[i]是我的车辆在车站维修的成本i.

我必须在第一个车站为我的车提供服务,我的车可以在车站之间最多行驶100英里.

什么是从高速公路开始到最后以最低成本获得最有效的算法(我需要知道要停在哪个站点)？我能够找到一个贪婪的解决方案来减少停止次数,但是以最低的成本,我正在考虑DP,具有最佳的子问题:

bestcost[j] = min( 0<i<j bestcost[i] + C[j] s.t. D[j]-D[i] <= 100)

并且有一个单独的数组last[j],其中包含要停止的最后一个站,这将是i从上面的子问题中最好的.

这是正确的方法,还是有更好的Greedy/DP解决方案？

给出M * N两个球员p1和p2网格的网格和位置.有n个球放在网格上的不同位置.让这些球的位置B(1), B(2), B(3) ..., B(n).

我们需要计算选择所有球所需的最小曼哈顿距离.球应该在如果即升序采摘B(i)的前采摘B(j)如果i < j.

考虑下面的示例情形:
p1 = (1, 1) p2 = (3, 4) 让我们考虑球的位置作为 B(1) = (1, 1), B(2) = (2, 1), B(3) = (3, 1), B(4) = (5, 5)
输出将5因为p1会先选择B(1), B(2), B(3)和p1将选择B(4)

我的方法
,我做了贪婪的 方法和计算距离p1,并p2从给定的球B(i)(从开始i = 1 to …

我在编程竞赛中遇到了这个问题:

我们给出一个由n个元素组成的数组.在每次迭代中,您可以选择任何两个元素一个_我和一个_Ĵ并更换一个_我有一个_我和一个_Ĵ.&是按位AND运算符.找到使所有数组元素为零所需的最小AND操作数.

假设存在给定输入的解决方案.这个问题的最佳解决方案是什么？

我有一个输入字符串,如"=== text ===和=== text ===",我想用相应的html标签替换wiki语法.

输入:

===text=== and ===text===

理想输出:

<h1>text</h2> and <h1>text</h2>

但是使用以下代码我得到了这个输出:

var regex = new Regex("---(.+)---");
var output = regex.Replace("===text=== and ===text===", "<h1>$1</h1>");

<h1>text=== and ===text</h1>

我知道问题是我的正则表达式与贪婪相匹配.但是如何让他们不贪心.

谢谢你,亲切的问候.丹尼

以下问题取自算法问题(问题653):

你被给予了2个数字矩阵.找到一个O(n log n)算法,该算法置换数组中的行,使得数组中的任何一列都不包含比⌈√n更长的子序列(可能不包含连续的数组元素).

我不知道如何解决这个问题.我认为它可能会使用某种分而治之的复发,但我似乎无法找到它.

有没有人有任何想法如何解决这个问题？

我有两个句子作为输入.比方说,举个例子:

<span>I love my red car.</span>
<span>I love my car.</span>

现在我想匹配span-tags内的每个textpart(如果有颜色).

如果我使用以下正则表达式:

/<span>(.*?)(?P<color>red)(.*?)<\/span>/ms

仅匹配具有颜色的线.所以我想让我们使用？-operator(一个或零).

/<span>(.*?)(?P<color>red)?(.*?)<\/span>/ms

现在两个行/句子都将匹配.可悲的是,颜色不再匹配了.

问题是为什么？通过使用 ".*？" 在颜色部分之前,我以为我已经使正则表达式非贪婪,所以颜色部分会匹配,如果它存在的话.但正如所说,它不......

在维基百科页面上,据说贪婪算法仅适用于具有最佳子结构的问题.

问题:

1. 什么是最优/非最佳子结构？
2. 什么是本地和全球最优？
3. 如何证明贪婪算法能够产生全局最优？

我希望有一个人可以帮助我。我正在研究 CS50x 并正在研究 Pset1 - 贪婪。每当我编译代码时，我都会收到以下错误：

/tmp/greedy-46be96.o: In function `main':
greedy.c:(.text+0x95): undefined reference to `round'
clang: error: linker command failed with exit code 1 (use -v to see invocation)

任何帮助将不胜感激。如果问题含糊不清，我深表歉意，我已尽力深入探讨。我在终端中使用了man round ，并到处搜索，尝试不同的解决方案，但没有任何效果。

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

int main(void)
{
    float owed;
    float change;
    float quarter = 0.25;
    float dime = 0.10;
    float nickel = 0.05;
    float penny = 0.01;

    do {
        printf("How much change is owed?: ");
        owed = GetFloat();

    } while(owed <= 0);

    change = round(owed …

给定 n 个塔的高度和一个值 k。我们需要将每个塔的高度增加或减少 k（仅一次），其中 k > 0。任务是最小化修改后最长和最短塔的高度之间的差异，并输出该差异。

我得到了解决方案背后的直觉，但我无法评论下面解决方案的正确性。

// C++ program to find the minimum possible 
// difference between maximum and minimum 
// elements when we have to add/subtract 
// every number by k 
#include <bits/stdc++.h> 
using namespace std; 
  
// Modifies the array by subtracting/adding 
// k to every element such that the difference 
// between maximum and minimum is minimized 
int getMinDiff(int arr[], int n, int k) 
{ 
    if (n == 1) 
       return 0; 
  
    // Sort all elements …