给定两个数组，找到索引乘积的最小和

Question

给定两个数组，找到索引乘积的最小和

6

假设我有两个大小相同的未排序数组，例如：

A = {1, 4, 3, 2}
B = {5, 12, 1, 5}

我希望找到每两个单元格的最小乘积和，即从每个数组中选出一个单元格进行相乘的总和，表示为A[i] * B[j]（其中i是A中的索引，j是B中的索引）。我应该用另一个数组中的哪些值与哪些值相乘，以获得最小的乘积和？请注意，一旦执行了A[i]*A[j]，就不能再次使用这些单元格。编辑：对于上面的示例，最小和为1*4 + 3*5 + 5*2 + 1*12 = 31。

- wannabe programmer

你想找出什么时候 A[i] * B[j] 是最小的可能值，或者是多个乘法的总和？ - David

1

你能更明确地提出你的问题吗？你能给出你的例子的答案吗？ - Thijs Riezebeek

2

将一个数组按升序排序，另一个数组按降序排序。现在...在每个索引处相应的元素相乘....等等...你能重复使用任何数组中的元素吗...??? - sarveshseri

1

因为...当一个更大的数字被乘以时...相比较于一个较小的数字，它会增长得更快。所以...为了最小化乘积输出的总和...你需要用较小的数字去乘以较大的数字。 - sarveshseri

1

假设存在两组配对情况，通过交换伙伴可以减少它们的乘积之和，为了证明将它们按逆序排列相乘可以得到最低可能的和，然后使用每个数组已知的排序顺序来证明任何这样的交换都会增加乘积之和（或在某些情况下保持不变）。基本上，证明将两个较大的数字相乘和两个较小的数字相乘将产生比对给定的2元素数组进行从大到小排序并交换伙伴所得到的更大的总和。因此，没有这样的配对可以交换以使总和更小。 - Rob Parker

显示剩余7条评论

3个回答

3

Aravol 提供了一些关于为什么反向排序匹配是最优的直觉，但对于这种情况，我认为真正严格证明它总是有效是有用的。

证明的一种方法是表明，给定任何不是已经反向排序的匹配，稍微更改该匹配使其“更像”反向排序匹配从不增加总和。如果我们可以表明此过程

可以从任何匹配开始，且
始终在反向排序匹配处终止，

那么我们已经表明反向排序匹配不比任何其他匹配更差-这与表明它具有最低可能总和相同。我想强调的是，任何算法都没有实际执行以下任何计算；对于证明的目的，我们所要做的就是表明它们可以被执行，并且如果这样做，则它们将具有所需的行为。

为此，让我们假设我们以一组对的形式给出任意匹配。首先，让我们按其第一个元素递增的顺序对它们进行排序。（我们可以这样做，因为列出对的顺序不影响它们的总和。）称排序后的第i对为（x [i]，y [i]）;根据定义，排序后我们有x [i] <= x [i + 1]对于所有i。现在，如果匹配尚未反向排序，则必须存在一对违反反向排序性质的相邻y值-即必须存在某个i使得y [i] 0，因此它们的乘积必须<= 0。换句话说，执行此交换永远不会增加总和。

但这是否会让我们更接近反向排序的匹配，从而实现终止呢？是的，因为重复执行查找违规然后交换的过程就像插入排序前i + 1个元素。让y [i + 1]的原始值为z。在交换y [i]和y [i + 1]之后，z的值刚刚在一对列表中向后移动了一个位置。如果我们重新运行查找第一个反向排序违规的过程，我们可能会发现它出现在i-1处（即，我们发现y [i-1]＜y [i]） - 在这种情况下，我们可以交换y [i-1]和y [i]，将z值再次向后移动一个位置。我们可以一直做到z到达y [1]，或者我们发现第一个位置j，使得y [j]＜y [j + 1]也具有属性y [j-1]≥y [j + 1]：后者意味着z值已经到达其最终位置，因为我们知道对于所有k＜j-1，y [k]≥y [j-1]。无论如何，在最多i次交换后，z将到达其最终位置，并且下一个违规查找运行将找到比原始i更晚的位置 - 或确定没有这样的位置（即y值现在反向排序）。

总之，在最多n ^ 2个查找违规-然后交换的操作之后，y值将以反向排序顺序排列，并且总数将不超过原始总数。由于我们没有对初始匹配做任何假设，因此该结果适用于任何给定的匹配，因此我们已经证明反向排序的匹配至少与所有匹配一样好。（请注意，此证明的任何方面都不依赖于数字是非负的，因此这也适用于包含负数的数组。）

- j_random_hacker

1

这个定理被命名为重排不等式

虚构证明：

有一个比@j_random_hacker的证明更简单的矛盾证明。

假设a按增序排序。

由于每个单元格最多只能触摸一次，因此一个选择对应于一个排列s，总和为f(s) = sum(a[i]*b[s(i)], i=1..n)

由于排列的数量是有限的，至少有一个最小值。

让我们称其中之一为s1。所以对于所有的s，f(s1)<=f(s)

我们可以将其转换为具有相同和f(s1)=f(s2)<=f(s)的排列s2，例如如果a[i]=a[i+1]，则b[s2(i+1)]>=b[s2(i)]（1），只需按照b的子数组[s1(k)]..b[s1(k+n)]的降序排序，其中a[k]=a[k+1]=..q[k+n]。

因此，f(s2)也是最小的。让我们通过反证法证明b(s2[k])是递减的。

假设存在i使得b[s2(i)]<b[s2(i+1)](2) 由于(1), a[i]!= a[i+1]

所以a[i]<a[i+1](3) 因此，根据(2)，b[s2(i)] - b[s2(i+1)]<0(4)

因此，由于 (3) 的结果，当 a[i] - a[i+1] < 0 (5) 时。

在这种情况下

a[i]*b[s2(i)]+a[i+1]*b[s2(i+1)]-(a[i]*b[s2(i+1)]+a[i+1]*b[s2(i)])
=a[i]*(b[s2(i)]-b[s2(i+1)])+a[i+1](b[s2(i+1)-b[s2(i)])
=(a[i]-a[i+1])(b[s2(i)]-b[s2(i+1)]) >=0 (because of  product of two negative number because of (4) and (5)

so  a[i]*b[s2(i)]+a[i+1]*b[s2(i+1)] - (a[i]*b[s2(i+1)]+a[i+1]*b[s2(i)])>0
so a[i]*b[s2(i)]+a[i+1]*b[s2(i+1)] > (a[i]*b[s2(i+1)]+a[i+1]*b[s2(i)]) (6)

让我们设置排列 s3，将 i 和 i+1 交换

s3(n) = i+1 if n = i
        i if n = i+1
        s2(n)

a[i]*b[s2(i)]+a[i+1]*b[s2(i+1)] > (a[i]*b[s3(i)]+a[i+1]*b[s3(i+1)])
and
a[n]*b[s2(n)]=s[n]*b[s3(n)] for n!= i and n!=i+1

so f(s2)>f(s3)

因此，s3比s2更好的排列方式。

存在矛盾，因此假设(2)是错误的。

因此，对于所有的i，b[s2(i)] < b[s2(i+1)] (2)是错误的。

因此，b[s2(i)] >= b[s2(i+1)] for all i。

因此，s2的b[s2(k)]按降序排列。因此，选择一个降序的b可以得到最佳结果。

类似的证明可以证明将a和b排序后的最大乘积总和。

- Xavier Combelle

提到重新排列不等式的名称是一个很好的回答。 - qwr

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David · Accepted Answer

为了找到最小的总和，将一个集合按升序排列，另一个按降序排列，然后沿着相似的索引进行乘法运算。

这是因为每个配对（由于需要为每个元素得出结果，对于固定的）的最小可能乘积是b[j]的最小可能值，反之亦然。

这也适用于负数，因为最大的负数是最小的数字，因此与相关数组中最正数的数字配对。即使两个集合完全为负数，这也会进一步继续，因为每个乘法的结果变得等同于当两个集合具有其值的负数时。