greedy 相关问题

贪心算法是一种算法，它遵循问题求解启发式，在每个阶段进行局部最优选择，希望找到全局最优。

使用 igraph 从 R 中具有最大权重的邻居创建子图

我正在尝试通过以下过程从图中的边对创建子图：图书馆（igraph）库（数据.表） dt <- data.table(from = c("A", "B", "C"...

r graph igraph greedy subgraph

回答 1 投票 0

在保存点有限的多分支游戏中最小化完成所有结局的时间的算法

在多分支游戏中，有 𝑛 种可能的结局。您可以将其视为具有 𝑛 叶节点的有向树，其中每条边的权重为 1。而不是玩整个游戏来重新...

algorithm tree dynamic-programming shortest-path greedy

回答 1 投票 0

增加三元组子序列 - 这个解决方案真的有效吗？为什么？

我一直在努力解决 leetcode 不断增加的三元组子序列问题。给定一串数字，必须找出其中是否有满足 a 的子序列我一直在努力解决leetcode的增加三元组子序列问题。给定一串数字，必须找出其中是否有满足a<b<c的子序列。数字不必连续，但索引需要排序；也就是说，由于 [1,2,0,3] 有效，因此 [1,2,3] 为 true，但 [3,2,1] 为 false。我们还被要求理想地找到一个以 O(n) 时间复杂度和 O(1) 空间复杂度运行的解决方案。找到一个足够好的解决方案来通过并阅读已接受的解决方案后，我发现公认的最有效的解决方案是以下的一些变体： var increasingTriplet = function (nums) { let a = Infinity, b = Infinity, c = Infinity; for (let i = 0; i < nums.length; i++) { if (nums[i] <= a) a = nums[i]; else if (nums[i] <= b) b = nums[i]; else if (nums[i] <= c){ return true; } } return false; } 虽然它确实通过了测试用例，但我不确定它是否正确。原因如下：考虑数组[20 100 10 12 5 13]。我们的结果对于该输入应该是正确的，因为 [10 12 13] 满足条件。对于该测试，该算法确实返回 true，但如果我们在成功时记录 a、b 和 c 的值，它们是 { a: 5, b: 12, c: 13 }，这不是正确的解决方案，因为这三个数字在原始数组。两种可能的情况之一正在发生：算法错误。该算法仅验证所需子集的存在，但它并没有真正找到它。我怀疑是后者，因为我无法构建一个算法给出错误结果的测试用例。然而，我无法理解为什么在我暴露的情况下它保证是正确的背后的直觉。我还想知道返回正确子集的算法是否可以在 O(n) 时间和 O(1) 空间中工作。您找到的解决方案代码是正确的。其背后的直觉是，如果 b 设置为输入数组中的某个值，那么您知道之前有一个较小的值并被分配给 a。如果稍后 a 获得较小的值，这不会改变当前 b 值仍然是之前发生的较小值的证明的事实 - 我们只是没有将其存储在 a 中不再了。如果在该状态下我们发现一个大于b的值，我们就证明存在递增三元组。我们可能不再引用该三元组中的第一个值，但这并不重要。我们拥有该三元组中的第二个这一事实就足以作为证据。注意：b的实际值保证在此“b”之前满足较小的值。 a的值可能会被后一个较小的值取代，但这一操作不会改变过去存在正确子序列older_a, b的事实

arrays algorithm greedy

回答 2 投票 0

我寻找最大独立集的贪心方法是最优的吗？

我正在执行一项任务，以找到图中最大的独立集。在研究了各种方法之后，我发现回溯经常被推荐，但它具有指数时间复杂度，

graph backtracking greedy independent-set

回答 1 投票 0

如何提高根据具体情况排砖的时间复杂度？

我正在解决一个问题，我需要将 N 个不同长度的砖块排列成最少数量的堆栈。堆砖的规则是，一块砖 𝑖 可以放置在砖块顶部 𝑗 只是...

python algorithm data-structures time-complexity greedy

回答 1 投票 0

为什么贪心启发式不能给出文件存储的最优解决方案？

为什么贪心启发式不能给出文件存储的最优解决方案？我正在解决一个问题，我需要在硬盘上存储大小为 $f_1、f_2、\ldots、f_n$$ 的 $n$ 文件。磁盘已损坏...

greedy heuristics

回答 1 投票 0

储备活动的活动选择问题

如何通过储备活动解决活动选择问题？假设我们选择了一组不重叠的活动。现在，对于每个 u_i 活动，我们需要选择储备活动

c++ algorithm greedy

回答 1 投票 0

平衡分区贪婪方法

我正在 en.wikipedia 和 MIT DP 笔记集中查看平衡分区问题（问题 7）。该问题基本上要求将给定的数字数组划分为 2 个子集......

algorithm dynamic-programming greedy

回答 2 投票 0

图顶点着色算法的布尔公式

我有一个有 5 个顶点的图。图 g1 = 新图(5); g1.addEdge(0, 1); g1.addEdge(0, 2); g1.addEdge(1, 2); g1.addEdge(1, 3); g1.addEdge(3, 2); ...

algorithm boolean-logic greedy graph-coloring

回答 2 投票 0

图形着色算法的布尔公式

我有一个有 5 个顶点的图。图 g1 = 新图(5); g1.addEdge(0, 1); g1.addEdge(0, 2); g1.addEdge(1, 2); g1.addEdge(1, 3); g1.addEdge(3, 2); ...

algorithm boolean-logic greedy graph-coloring

回答 2 投票 0

找出店主通过一定数量的销售可以赚到的最高金额

我最近在一次求职面试中遇到了一个编码问题，得到了正确的结果，但我的代码不够快，他们没有告诉我原因。想象一下有一个贪婪的店主有一堆......

java greedy

回答 1 投票 0

在sscanf()中使用时，%s在遇到%s后面的符号时不会停止匹配[重复]

我尝试使用 sscanf() 用 php 解析字符串： $n = sscanf($line, "%s.%s.%s=%s", $ws, $layer, $perm, $role); echo $ws。” - “.$layer。” - “.$perm。” - “.$role。” ”; 并得到输出： *.*.r=* - - - t...

php scanf greedy

回答 4 投票 0

防止 sscanf() 使用 %s 占位符消耗“-”[重复]

可以区分小数和'-' $str = "1995-25"; $pat = sscanf( $str , "%d-%d); print_r($帕特); 它还可以区分第一个“-”和后面的字符串 $str =“-of&...

php scanf greedy

回答 1 投票 0

%s 不会停止在模式 [已关闭] 中的硬编码管道处匹配

所以我有很多带有格式化信息的文件，所以有几个文件包含这种格式的多行： ID|访问次数|信息|姓名当我运行以下代码时，$id 和 $visits 匹配正确...

php scanf greedy

回答 2 投票 0

如何找到满足加油站（Leetcode）问题的所有点？

我想解决与https://leetcode.com/problems/gas-station/description/问题类似的问题：给定环形路线上的 n 个加油站，第 i 个加油站有 g[i] 个加油站。旅行费用...