你好，我刚刚开始学习贪心算法，我首先研究了经典的硬币兑换问题。我可以理解算法中的贪婪（即，选择局部最优解以获得全局最优解），因为我选择硬币的最高值，使得 sum +{所选硬币的值}<=total value。然后我开始解决一些网站上的一些贪心算法问题。我可以解决大部分问题，但无法弄清楚贪婪到底在哪里在问题中应用的具体位置。我针对这些问题编写了我能想到的唯一解决方案并得到了接受。社论也展示了解决问题的相同方法，但我无法理解贪婪范式在算法中的应用。
贪心算法是解决特定范围问题的唯一方法吗？或者它们是解决问题的一种更有效的方法？
您能否给我使用和不应用贪婪范式的同一问题的伪代码？
我有 X 名学生，其中 X 是 6 的倍数。我现在想将学生分成 6 人一组。
我有一个函数可以衡量 6 人一组的“好”程度（假设它是一个目前以恒定时间运行的黑匣子）。通过将学生分开，然后对每个组调用我的函数来衡量其优点，然后总结每个组的优点，我就能够衡量一组特定组的“好”程度。
我正在尝试创建一种算法，以某种方式对学生进行分组，以使所有组的总优点最大化，并且没有组的个体优点低于某个值 y。换句话说，将学生分成 6 人一组，以在所有组的优度都高于 y 的约束下最大化总优度。
我预计运行该算法的学生数量 (X) 约为 36 人。
这个问题似乎是 NP 完全的，所以我同意采用启发式算法。我对此没有太多经验，但我认为某种遗传算法或模拟退火甚至贪婪算法可能会起作用，但我不确定从哪里开始我的研究。
有人可以指出我正确的方向吗？我做了一些研究，这个问题似乎与旅行商问题几乎相同（问题空间是学生/节点的所有排列），但我不认为我可以将 TSP 算法应用于此，因为“节点”的数量“（大约 36）对于任何有效的东西来说都是相当大的。
algorithm computer-science simulated-annealing greedy genetic-algorithm
我有以下问题：
解决背包0-1问题（不是分数） 假设每个物体都有重量
w1或w2（只有两个重量）。容量=W，算法必须运行在O(nlogn)上。
我尝试解决，贪心算法不行，动态规划算法是O(n*W)。
谁能给我提示。谢谢。
algorithm knapsack-problem dynamic-programming greedy time-complexity
例如，与
k=10
A=[2,1,3]
B=[7,8,9]
答案是肯定的，因为您可以重新排列元素
A=[1,2,3]
B=[9,8,7]
A[i]+B[i] >= 10 = k那么对于来说这是真的i=0,1,2。我的算法是贪心的，就像
int k = parameters[1];
int[] A = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
int?[] B = Array.ConvertAll(Console.ReadLine().Split(' '), Extensions.ToNullableInt);
Array.Sort(B);
for(int j = 0; j < A.Length; ++j)
{
bool found = false;
for(int m = 0; j < B.Length && !found; ++j)
{
if(B[m] == null)
continue;
if((A[j] + B[m]) >= k)
{
found = true;
B[m] = null;
}
}
if(!found)
{
Console.WriteLine("NO");
return;
}
} …我正在阅读有关Binary search 的不同材料，我不清楚它是一个贪婪的二进制（在我看来不是），或者，它可以是具有某些特定实现的贪婪算法吗？
如果它可以是贪婪的，它如何有意义？如果通过选择局部最优获得全局最优，不重新考虑以前的选择，就不能保证二分查找的正确结果。
输入
\n\n\n(1)汽车满油箱可行驶的最大距离：L公里；
\n(2) 一个整数数组，[0, x1, x2, \xe2\x80\xa6, xn, xn+1]，每个整数代表一个位置到源点A的距离。第一个整数为0，即A和A之间的距离。第二个距离x1，表示第一个加油站和A之间的距离。A和B（目的地）之间有n个加油站。xn是最后一个加油站到A的距离，xn+1是B到A的距离。
\n(3)n，为加油站数量。
\n
输出
\n\n\n从 A 到 B 的最少补充次数
\n
代码
\nnumRefills = 0\ncurrentPosition = 0\n\nwhile(currentPosition <= n){\n lastPosition = currentPosition\n\n while(currentPosition <= n && x[currentPosition + 1] \xe2\x80\x93 x[lastPosition] <= L) {\n currentPosition++;\n }\n\n if (currentPosition == lastPosition) return IMPOSSIBLE; \n if (currentPosition <= n) numRefills ++;\n}\n\nreturn numRefills\n我的疑问是：
\n\n\n
- 为什么上面代码的时间复杂度是O(n)？至少因为嵌套的 while 循环，它不应该是 O(n^2) 吗？
\n- 如何证明“在最远的距离加气”是安全的举动？
\n- 除了使用 …
该问题应该具有哪些属性,以便我可以决定使用动态编程或贪婪方法的方法？
我对正则表达式很有经验,但我对当前涉及析取的应用程序有一些困难.
我的情况是这样的:我需要根据地址的"标识符元素"上的正则表达式匹配将地址分成其组成部分 - 类似的英语示例可能是"state","road"或" boulevard" - 例如,我们在地址中写了这些内容.想象一下,我们有一个类似下面的地址,其中(这在英语中永远不会发生),我们在每个名称后面指定了标识符类型
United States COUNTRY California STATE San Francisco CITY Mission STREET 345 NUMBER
(CAPS中的单词是我所谓的"标识符").
我们想将其解析为:
United States COUNTRY
California STATE
San Francisco CITY
Mission STREET
245 NUMBER
好吧,这对于英语来说当然是设计的,但这里有一个问题:我正在处理中文数据,实际上这种标识符规范的风格一直在发生.以下示例:
??-? ; ??-? ; ??-? ; ??-? ; ??-? ;
Yunnan-Province ; LiJiang-City ; GuCheng-District ; Xi'An-Street ; Yangchun-Alley
这很容易 - 对潜在的候选标识符名称进行惰性匹配,分为分离列表.
对于中国,以下是"省级"实体:
? (Province) ,
??? (Autonomous Region) ,
? (Municipality)
所以我的正则表达式到目前为止看起来像这样:
(.+?(?:(?:?)|(?:???)|(?:?)))
我有一系列这些,以便考虑地址的不同部分.例如,对应于城市的下一级是:
(.+?(?:(?:??)|(?:???)|(?:?)|(?:?)))
因此,要匹配省实体,然后是城市实体:
(.+?(?:(?:?)|(?:???)|(?:?)))(.+?(?:(?:??)|(?:???)|(?:?)|(?:?)))
使用命名捕获组:
(?<Province>.+?(?:(?:?)|(?:???)|(?:?)))(?<City>.+?(?:(?:??)|(?:???)|(?:?)|(?:?)))
对于上述情况,这会产生:
$+{Province} = ???
$+{City} = …
我有一些示例问题，正在为它们编写伪代码，并且注意到了贪婪技术和穷举搜索之间的令人震惊的模式。
Job 1, Job 2, Job 3, Job 4, Job 5
Person: 1 9 2 7 8
Person: 2 6 4 3 7
Person: 3 5 8 1 8
Person: 4 7 6 9 4
上面是分配问题的表格示例。基本上，您有n份工作要做，这里有5份工作，并且您需要用最少的工作量完成它们，前提是时间由表中每个人及其工作的附加值显示。
似乎穷举搜索和贪婪技术的唯一区别在于两者用来解决问题的数据结构。贪婪使用加权图，而穷举使用数组。这在我们的算法中会发生很多吗？是否有许多算法相互模仿，却只是使用更有效的数据结构来解决我们的问题？