有两个长度为N的整数序列A []和B [],都是未排序的.
要求:通过交换A []和B []之间的元素(可以随机交换,而不是使用相同的索引),将{A []}中所有元素的总和与{B中所有元素的总和[]}最小化.
PS:实际上,这是我遇到的面试问题.
非常感谢
小智 6
这将是NP难!我相信你可以从Subset Sum减少到这个.
根据BlueRaja/polygene的评论,我将尝试从Subset Sum中完全减少.
这是一个减少:
子集和问题:给定整数x 1,x 2,...,x n,是否有一些非空子集总和为零？
我们的问题:给定两个大小为k的整数数组,找到两个数组之和的最小可能差异,假设我们可以在数组中的整数中进行混洗,将两个数组视为一个数组.
假设我们的问题有一个多项式时间算法.
说现在给你整数T = {x 1,x 2,...,x n }(multiset)
令S i = x 1 + x 2 + ... + x n + x i.
令T i = {x 1,x 2,...,x i-1,x i + 1,...,x n }(= T - x i)
限定
A i =使用T i形成的阵列
B i = [S i,0,...,0](即一个元素是S i,其余是零).
设m i =由阵列A i和B i的问题找到的最小差异
(我们运行我的问题n次).
声明:当且仅当有一些i时,T的一些非空子集合为零,其中m i = 0.
证明:(wlog)说x 1 + x 2 + .. + x k = 0
然后
A = [x k + 1,...,x n,0,... 0]
B = [X 2,X 3,...,X ķ,S 1,0,..0]
给出最小差值m 1为| x 2 + .. + x k +(x 1 + ... + x n)+ x 1 - (x k + 1 + .. + x n)| = | 2(x 1 + x 2 + .. x k)| = 0.
类似地,可以证明if部分.
实际上,这实际上也跟随(更容易)来自Partition:只需创建全零的新数组.
好吧,我没有犯任何错误.