贪婪算法，最小化排列的总和
我有一个数组｛a1，a2，…，an｝（自然数），我需要构建一个贪婪的算法，找到1…n的排列（i1，…in），使和最小：1.ai1 2.ai2……（n− 1） 艾因−1 n.ain。
当然，我可以尝试所有这些，并选择一个给出最小的总和（这将在O（n！）中给出正确的结果）。
我贪婪的选择是按降序选择数字，但我不知道如何证明这是有效的。
页（page的缩写）这只是为了学习和训练，我不能“贪婪地”思考
共有1个答案
按降序选择数字是最佳的。
通过对n的归纳来证明：假设有一个排列是最优的，并且最小的数字不在最后一位。然后，交换最后一个元素和最小的元素会减少总和。这与最优性的假设相矛盾，所以我们必须知道最小的元素在最后。根据归纳假设，其他元素在前（n-1）个位置按降序排列。
n=1 的基本情况是微不足道的。
-
输入是实数x1、x2、…、x2n的序列。我们想把这些数字配对成n对。对于第i对（i=1，2，…，n），让Si表示该对中的数字之和。（例如，如果将x（2i−1） 并且x2i作为第i对，Si＝x（2i−1） x2i）。我们希望将这些数字配对，以使Maxi[Si]最小化。设计一个贪婪算法来解决这个问题。 这就是问题所在；我的解决方案是简单地对数字进行排序，并将前一个元素与后一个元素配对，加一个/减一个索
-
本文向大家介绍贪婪算法相关面试题，主要包含被问及贪婪算法时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策
-
有人有线索为什么它对案件2不起作用吗？非常感谢你的帮助。编辑：案例2的预期结果是6130美元。我好像得到了6090美元。
-
以下是我需要咨询以寻求帮助的问题： 编写一个贪婪算法，使用贪婪算法以尽可能少的硬币进行兑换。您将获得一个硬币值数组和一个金额：。返回一个包含每个硬币计数的数组。 例如：应该返回数组，该数组指示每枚硬币的数量：2枚50美分硬币，1枚25美分硬币，1枚10美分硬币），没有镍币（5美分），和2便士（1美分），加起来是137美分。 从computeChange返回的数组应该与第一个参数（硬币）的长度相同。
-
任务是典型的背包问题。求解时应采用贪婪算法。我设法创建了下面的代码，但它工作得太慢了。你能告诉我怎么加快速度吗？谢谢你。 c是背包的重量限制。n表示价格权重对的数量（这两个数字都是int类型，而不是float）。限制如下：（1）如果在相同重量的元素之间选择，价格最高的元素应该被取；（2）如果在相同价格和相同重量的元素之间选择，第一个输入的元素应该被取。
-
设计算法以实现给定问题的最佳解决方案。 在贪婪算法方法中，决策是从给定的解决方案域做出的。 由于贪婪，选择了似乎提供最佳解决方案的最接近的解决方案。 贪心算法试图找到一个本地化的最优解决方案，最终可能导致全局优化的解决方案。 但是，通常贪婪算法不提供全局优化的解决方案。 计数硬币 这个问题是通过选择最不可能的硬币来计算到期望的值，并且贪婪的方法迫使算法选择最大可能的硬币。 如果我们提供₹1,2,5