给定一个由 n 个整数组成的数组 arr,重新排列它们,以便最小化以下方程。
sigma i=0 到 n-1,
arr[i]*arr[i+1]
示例: n=7 ar=1,10,2,7,10,6,6
答案:127(最佳排列为10,1,7,6,6,2,10)
通过查看这个示例,它看起来只是调整相邻单词的最大和最小元素,但这对于下面的示例不起作用
示例2:
arr=2,4,10,9,3
答案:67(最佳排列:10,2,4,3,9)
通过这个例子,逻辑看起来只是将最大元素放在两端,并将最小->最大表单边框排列到中间。但这同样并不适用于所有情况。 事实上,这些是整数,意味着可能有负值,这使得它变得更加困难。帮帮我:)
我已经尝试过:
简单的贪婪方法:最初,我们尝试了一种贪婪策略,包括对数组进行排序并将最小和最大元素配对来计算乘积和。事实证明,这种方法不是最理想的,因为它并不总是产生最小可能的总和,特别是在最大数字不应该与最小数字配对的情况下。
细致入微的贪婪方法:我们通过将最大的数字放置在结果数组的一端并将第二大的数字放置在最小的数字旁边来改进贪婪方法。该策略旨在通过将最大数量与尽可能最小的对应物配对来最大程度地减少最大数量的影响。虽然这种启发式方法比最初的简单配对更加细致,但它仍然不能始终提供最佳解决方案。
同时从两端贪婪。
重复直到完成。
例如1,10,2,7,10,6,6
10, ..., 10
10, 1, ..., 2, 10
10, 1, 7, ..., 6, 2, 10
10, 1, 7, 6, 6, 2, 10; sumproduct is 10+7+42+36+12+20 = 127