有两个长度为N的整数序列A[]和B[]，两者都是未排序的。
要求：通过交换A[]和B[]之间的元素（可以随机交换，但不能交换相同索引处的元素），使得{A[]中所有元素的总和}与{B[]中所有元素的总和}之差最小。
PS：实际上，这是我遇到的一道面试题。
非常感谢。
需要一个算法来解决这个问题。
8
- Heisenburgor
9
1交换操作是否必须在每个序列的相同索引处进行？ - Joe Phillips
2如果你想得到一些认真的回答，那么你真的需要添加更多的细节。 - Jason Hall
5我们不在这里为你做功课。 - Jason
8请就目前的解决方案提出您的想法。社区希望与您合作，而不是为您服务。 - fbrereto
@fbrereto：有人告诉我这个问题与NP-完全相关，我对此感到困惑。 - Heisenburgor
显示剩余4条评论
6个回答
6
这将是NP难问题！我相信你可以从子集和 进行规约。
根据BlueRaja/polygene的评论，我将尝试提供来自子集和的完整规约。
这是一个规约：
子集和问题：给定整数x1，x2，...，xn，是否存在一些非空子集其总和为零？
我们的问题：给定大小为k的两个整数数组，假设我们可以在数组中移动整数并将两个数组视为一个数组，找到两个数组之和的最小可能差。
假设我们有一个多项式时间算法解决了我们的问题。
现在假设你有整数T = {x1，x2，...，xn}（multiset）
令Si = x1 + x2 + ... + xn + xi。
令 Ti = {x1, x2, ..., xi-1, xi+1, ..., xn } ( = T - xi)
定义
Ai = 使用 Ti 形成的数组
Bi = [Si, 0, ..., 0] （即一个元素是 Si，其余为零）。
让 mi = 我们的问题在数组 Ai 和 Bi 中找到的最小差异
（我们运行我们的问题 n 次）。
声明：当且仅当存在某个 i，使得 mi = 0 时，T 的一些非空子集总和为零。
证明：（wlog）假设 x1 + x2 + .. + xk = 0
那么
A = [xk+1, ..., xn, 0, ...0]
B = [x2, x3, ..., xk, S1, 0, ..0]
给出最小差值 m1 的公式为 |x2 + .. + xk + (x1 + ... + xn) + x1 - (xk+1 + .. + xn)| = |2(x1+ x2 + .. xk)| = 0。
同样，可以证明它的逆命题。
实际上，这也可以更容易地从 Partition 推导出来：只需创建一个全零数组即可。
希望我没有犯任何错误。
- Aryabhatta
5
这相当于将A和B的内容放在一个集合中，然后执行np-hard的装箱操作。 - Justin R.
@fatcat1111：你需要换一种方式来证明NP难度。将一个难问题简化到当前问题。在这种情况下，子集和问题很容易被简化成这个问题。 - Aryabhatta
@polygenelubricants：我已经编辑了答案，指向了包含此信息的维基页面。 - Aryabhatta
这不是分区问题 - 在这种情况下，“一半”的大小是固定的。 - BlueRaja - Danny Pflughoeft
@BlueRaja，@polygenelubricants：我已经编辑了帖子以显示减少。 - Aryabhatta
3
任意选择一个NP完全问题，比如分割问题：将正整数的多重集合A划分为两个具有相同和的多重集合B和C，如{a1,a2,...,an}。添加n个零{0,0,0...,0,a1,...,an}，然后询问是否可以将该集合划分为具有相同和和相同元素数量的两个多重集合A和B。我声称这两个条件是等价的：
- 如果A和B是问题的解，则您可以划掉所有零并得到分割问题的解。 - 如果存在分割问题的解，例如ai1 + ai2 + ... aik = aj1 + ... +ajl，其中 {ai1, ai2, aik, aj1, ..., ajl} = {a1, ... , an}，则显然k+l = n。在左侧添加l个零，在右侧添加k个零，您将得到0 + ... + 0 + ai1 + ai2 + ... aik = 0 + ... + 0 + aj1 + ... +ajl，这是问题的解。
因此，这是一种约简（所以问题是NP-hard），并且该问题是NP，因此它是NP-complete。
- 如果A和B是问题的解，则您可以划掉所有零并得到分割问题的解。 - 如果存在分割问题的解，例如ai1 + ai2 + ... aik = aj1 + ... +ajl，其中 {ai1, ai2, aik, aj1, ..., ajl} = {a1, ... , an}，则显然k+l = n。在左侧添加l个零，在右侧添加k个零，您将得到0 + ... + 0 + ai1 + ai2 + ... aik = 0 + ... + 0 + aj1 + ... +ajl，这是问题的解。
因此，这是一种约简（所以问题是NP-hard），并且该问题是NP，因此它是NP-complete。
- sdcvvc
4
是的，这是有两个分区必须具有相同数量元素的分区问题。因此，它是NP-Complete。 - Justin Peel
1@Justin：这不是分区问题，因为你刚才提到的原因。@sdcvvc：你从这个问题给出了一个到分区问题的约简（证明了什么都没有），而不是相反。例如，假设我们有{1, 2, 3, 4, 5, 15}。这个问题的解决方案将给我们{1, 2, 15}，{3, 4, 5}。有没有办法利用这些信息来确定是否存在两个子集具有相同的和？ - BlueRaja - Danny Pflughoeft
@BlueRaja，好的，我想我一定误解了被问到的问题。我会再仔细看一遍。 - Justin Peel
+1 你说服我这是NP完备问题。这个答案值得一个✔️。 - BlueRaja - Danny Pflughoeft
2
“长度为 N 的序列 A[] 和 B[]” -> 这是否意味着 A 和 B 都是长度为 N？
（为了清晰起见，以下我使用以 1 为基础的数组）
如果是这样，那么如下所述：
（为了清晰起见，以下我使用以 1 为基础的数组）
如果是这样，那么如下所述：
- 假设 A[1..N] 和 B[1..N]
- 将 A 和 B 连接成一个新数组 C，长度为 2N：C[1..N] <- A[1..N]; C[N+1 .. 2N] <- B[1..N]
- 按升序排序 C。
- 从 C 中取出第一对数字；把第一个元素 (C[1]) 发送到 A[1]，第二个元素 (C[2]) 发送到 B[1]
- 取出第二对数字；这次发送第二个元素 (C[4]) 到 A[2]，第一个元素 (C[3]) 到 B[2]（发送到 A 和 B 的一对元素的顺序与步骤 3 中相反）
- ... 重复执行步骤 3 和 4，直到 C 被用尽
- Parijat
1
试着贪心一点。鉴于信息有限，我不确定还能提供什么其他的建议。
- JB King
0
我不确定这是否能确保最小可能的距离，但我脑海中首先想到的是类似于这样的东西：
int diff=0;
for (int i = 0; i<len; i++){
int x = a[i] - b[i];
if (abs(diff - x) > abs(diff + x)){
swap(a,b,i);
diff-=x;
}else{
diff+=x;
}
}
假设您有一个交换函数，该函数接受两个数组并交换位置i上的项目 :)
计算并添加位置i上两个值之间的差异，您将获得两个数组元素总和之间的增量差异。
在每个步骤中，您都要检查是更好地添加(a[i]-b[i])还是(b[i]-a[i])。如果是b[i]-a[i]的情况，则交换数组中位置i上的元素。
也许这不是最好的方法，但它应该是一个开始 :)
- garph0
0
这个问题是NP-完全问题。
我们可以将划分问题简化为此问题的决策版本，即给定两个相同大小的整数数组，确定是否可以交换项目使得和相等。
划分问题的输入：整数集合S，大小为N
为了将此输入转换为我们问题的输入，我们定义A为S中所有项目的数组，B为大小相同的数组，对于所有i，B[i]=0。该转换在输入大小上是线性的。
很明显，如果有一个由S划分成2个子集的方案使得它们的和相等，则我们应用于A和B的算法返回true。
- Eyal Schneider
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接