Besoin d'un algorithme pour ce problème - algorithme

Il existe deux séquences entières A [] et B [] de longueur N, les deux non triées.

Exigence: en échangeant des éléments entre A [] et B [] (échange aléatoire, pas avec le même index), faites la différence entre {la somme de tous les éléments de A []} et {la somme de tous les éléments de B [] } être minimum.

PS: en fait, c'est une question d'entrevue que j'ai rencontrée.

Merci beaucoup

Réponses:

6 pour la réponse № 1

Cela va être NP-difficile! Je crois que vous pouvez faire une réduction de Somme de sous-ensemble pour ça.

Selon les commentaires de BlueRaja / polygene, je vais essayer de fournir une réduction complète du total de sous-ensembles

Voici une réduction:

Problème de somme de sous-ensemble: Nombre entier donné x₁, X₂, ..., X_n, existe-t-il un sous-ensemble non vide qui revient à zéro?

Notre problème: Etant donné deux tableaux entiers de taille k, trouvez la différence minimale possible de la somme des deux tableaux, en supposant que nous puissions mélanger les entiers dans les tableaux, en traitant les deux tableaux comme un tableau.

Supposons que nous ayons un algo de temps polynomial pour notre problème.

Disons maintenant qu'on vous donne des entiers T = {x₁,X₂, ...,X_n} (multiset)

Soit S_je = x₁ + x₂ + ... + x_n + x_je.

Laisser t_je = {x₁, X₂, ..., X_i-1, X_{i + 1}, ..., X_n } (= T - x_je)

Définir

UNE_je = Tableau formé à l'aide de T_je

B_je = [S_je, 0, ..., 0] (c’est-à-dire qu’un des éléments est S_je et le repos sont des zéros).

Laisse moi_je = la différence minimale trouvée par notre problème pour les tableaux A_je et B_je

(nous courons notre problème n fois).

Revendication: Un sous-ensemble non vide de T somme à zéro si et seulement si,_je = 0.

Preuve: (wlog) dire x₁ + x₂ + .. + x_k = 0

alors

A = [x_{k + 1}, ..., X_n, 0, ... 0]

B = [x₂, X₃, ..., X_k, S₁, 0, ..0]

donne la différence minimale m₁ être | x₂ + .. + x_k + (x₁ + ... + x_n) + x₁ - (X_{k + 1} + .. + x_n) | = | 2 (x₁+ x₂ + .. x_k) | = 0.

De même, la partie if peut être prouvée.

En fait, cela découle aussi (plus facilement) de Partition: créez simplement un nouveau tableau avec tous les zéros.

Heureusement, je n’ai commis aucune erreur.

---

3 pour la réponse № 2

Prenez n'importe quel exemple de NP-complete problème de partition:

Partitionner un multiset A d'entiers positifs en deux multisets B et C avec la même somme

comme un₁,une₂,...,une_n}. Ajouter n zéros {0,0,0 ..., 0, a₁,...,une_n} et demandez si l'ensemble peut être partitionné en deux multisets A et B avec la même somme et le même nombre d'éléments. Je prétends que ces deux conditions sont équivalentes:

• Si A et B sont une solution au problème, vous pouvez rayer les zéros et obtenir une solution au problème partiel.
• S'il y a une solution au problème de la partition, par exemple un_i1 + un_i2 + ... a_Ik = un_j1 + ... + a_jl où un_i1, une_i2, une_Ik, une_j1, ..., une_jl} = {a₁, ... , une_n} alors évidemment k + l = n. Ajoutez l zéros sur le côté gauche et k zéros sur le côté droit et vous obtiendrez 0 + ... + 0 + a_i1 + un_i2 + ... a_Ik = 0 + ... + 0 + a_j1 + ... + a_jl, qui est une solution à votre problème.

Donc, ceci est une réduction (donc le problème est NP-difficile) et le problème est NP, donc NP-complet.

---

2 pour la réponse № 3

"séquences A [] et B [] de longueur N" -> cela signifie-t-il que A et B sont tous deux chaque de longueur N?

(Par souci de clarté, j'utilise des tableaux basés sur 1 ci-dessous).

Si oui, que diriez-vous de ceci:

1. Supposons A [1..N] et B [1..N]
2. Concaténer A et B dans un nouveau tableau C de longueur 2N: C [1..N] <- A [1..N]; C [N + 1 .. 2N] <- B [1..N]
3. Triez C par ordre croissant.
4. Prends le premier paire des nombres de C; envoie le premier élément (C [1]) à A [1] et le deuxième élément (C [2]) à B [1]
5. Prenez la deuxième paire de nombres de C; cette fois envoyer le seconde élément (C [4]) à A [2] et le premier élément (C [3]) à B [2] (l'ordre des éléments du couple envoyé à A et B est l'inverse de 3)
6. ... répétez 3 et 4 jusqu'à ce que C soit épuisé

L'observation ici est que, dans un tableau trié,une paire adjacente de nombres aura la plus petite différence (comparée à une paire de nombres de positions non adjacentes). L'étape 3 garantit que A [1] et B [1] consistent en une paire de nombres avec le moins de différence possible. L'étape 4 garantit que (a) A [2] et B [2] consistent en une paire de nombres avec la différence la plus petite possible (par rapport aux nombres disponibles) et aussi (b) que la différence est opposée dans le signe de l'étape 3. En En continuant ainsi, nous nous assurons que A [i] et B [i] contiennent des nombres avec le moins de différence possible. De plus, en inversant l'ordre dans lequel nous envoyons les éléments à A et à B, nous nous assurons que la différence change de signe pour chaque i successif.

---

1 pour la réponse № 4

Essayez d'être gourmand à ce sujet. Compte tenu de ces informations limitées, je ne suis pas sûr de savoir quoi d’autre.

---

0 pour la réponse № 5

Je ne suis pas sûr que cela garantisse la distance minimale possible, mais la première chose qui me vient à l’esprit est la suivante:

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;
}

}

en supposant que vous ayez une fonction d'échange qui prend les deux tableaux et échange les éléments en position i

En calculant et en ajoutant la différence entre les deux valeurs en position i, vous obtenez la différence incrémentale entre les sommes des éléments des deux tableaux.
à chaque étape, vous vérifiez s'il est préférable d'ajouter (a [i] -b [i]) ou (b [i] -a [i]). Dans ce cas, vous permutez les éléments situés à la position i dans les tableaux.

Ce ne sera peut-être pas la meilleure solution, mais cela devrait être un début :)

---

0 pour la réponse № 6

Le problème est NP-Complete.

Nous pouvons réduire le problème de partition au version de décision Pour résoudre ce problème, c’est-à-dire si deux tableaux d’entiers de même taille sont déterminés, déterminez si les éléments peuvent être échangés de manière à ce que les sommes soient égales.

Le problème de la partition: un ensemble S d’entiers, de taille N

Afin de transformer cette entrée en une entrée pourNotre problème, nous définissons A pour être un tableau de tous les éléments de S, et B un tableau de la même taille, avec B [i] = 0 pour tout i. Cette transformation est linéaire dans la taille d'entrée.

Il est clair que notre algorithme appliqué sur A et B renvoie true si et seulement si il existe une partition de S en 2 sous-ensembles tels que les sommes soient égales.

---