贪婪算法，将数字配对，最小化最大总和
输入是实数x1、x2、…、x2n的序列。我们想把这些数字配对成n对。对于第i对（i=1，2，…，n），让Si表示该对中的数字之和。（例如，如果将x（2i−1） 并且x2i作为第i对，Si＝x（2i−1） x2i）。我们希望将这些数字配对，以使Maxi[Si]最小化。设计一个贪婪算法来解决这个问题。
这就是问题所在；我的解决方案是简单地对数字进行排序，并将前一个元素与后一个元素配对，加一个/减一个索引，然后重复。该算法试图为每一对进行优化，从而使其变得贪婪。我只是想知道是否有线性时间算法可以做到这一点？
PS：这不是家庭作业，但我知道这看起来很像。
共有2个答案
如果你想贪婪和近似，你可以对数据运行一个固定大小的窗口，一次，并且只在窗口中配对数字 - 窗口左端的数字与窗口中的任何其他数字配对 - 标记不在左端的那个，这样你就不会重复使用它，并前进窗口， 所以左端的那个不会被重复使用。从局部最优的意义上说，这是贪婪的。如果你知道列表是均匀随机的，它可能是接近的，而且它是线性的，因为对一个长度恒定的列表进行排序 k 是相对于 N 的恒定时间。有了关于列表分布的其他知识，你可以使用一个仍然是 O（N） 并且只是近似的变体。
不，不可能有线性时间算法来帮你完成这件事。输入的数字可以是任何顺序，所以你不能马上用min-Maxi[Si]完成配对。您当前的解决方案简单而好。
改进运行时间的建议：
您可以使用输入数字创建二叉树（这需要O（nlog（n））时间）。对树进行顺序遍历并从（第一个i，最后一个i）元素创建对（i从0到n/2）
-
我有一个数组（自然数），我需要构建一个贪婪的算法，找到1…n的排列（i1，…in），使和最小：。 当然，我可以尝试所有这些，并选择一个给出最小的总和（这将在O（n！）中给出正确的结果）。 我贪婪的选择是按降序选择数字，但我不知道如何证明这是有效的。 页（page的缩写）这只是为了学习和训练，我不能“贪婪地”思考
-
用餐问题: 几家人一起出去吃饭。为了增加他们的社会交往，他们愿意坐在桌子上，这样同一家庭的两个成员就不会在同一张桌子上。假设晚餐特遣队有家庭，而家庭有成员。另外，假设有桌可用，并且第1桌的座位容量为。 问题是：我们可以坐在桌子上的最多人数是多少？ 编辑：创建一个图并运行最大流算法可以解决这个问题。但如果我们用Dinic算法有2*10^3个顶点，则全局复杂度为O(10^6*10^6)=O(10^12
-
本文向大家介绍贪婪算法相关面试题，主要包含被问及贪婪算法时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策
-
有人有线索为什么它对案件2不起作用吗？非常感谢你的帮助。编辑：案例2的预期结果是6130美元。我好像得到了6090美元。
-
给定一个数字向量，我想找到大小为2的组合中最小的绝对差异。然而，摩擦点伴随着使用来创建保持成对的矩阵。当矩阵/向量太大时，如何处理问题？ 当使用得到的对数（列数）太大时，我得到以下错误： 矩阵中的错误（r，nrow=len.r，ncol=count）：无效的“ncol”值（太大或NA） 这篇文章指出，矩阵的大小限制大约是10亿行和两列。 这是我使用的代码。抱歉在我的函数输出中使用了——我正在解决H
-
任务是典型的背包问题。求解时应采用贪婪算法。我设法创建了下面的代码，但它工作得太慢了。你能告诉我怎么加快速度吗？谢谢你。 c是背包的重量限制。n表示价格权重对的数量（这两个数字都是int类型，而不是float）。限制如下：（1）如果在相同重量的元素之间选择，价格最高的元素应该被取；（2）如果在相同价格和相同重量的元素之间选择，第一个输入的元素应该被取。