Somme de sous-ensemble d'un sous-ensemble de taille

Pour k=4, espace de complexité O(n), temps de complexité O(n ² * log(n))

trier le tableau. À partir de 2 plus petits et 2 plus grands éléments, calculer toutes les lesser sommes de 2 éléments (a[i] + a[j]) dans l'ordre non décroissant et toutes les greater sommes de 2 éléments (a[k] + a[l]) dans l'ordre non-croissant. Augmentation lesser somme si la somme totale est inférieure à zéro, diminution greater un si total la somme est supérieure à zéro, arrêt lorsque la somme totale est égale à zéro (succès) ou a[i] + a[j] > a[k] + a[l] (échec).

le truc est d'itérer à travers tous les index i et j de telle manière que (a[i] + a[j]) ne diminuera jamais. Et pour k et l , (a[k] + a[l]) ne devrait jamais augmenter. Une file d'attente de priorité permet de faire ceci:

1. Mettre key=(a[i] + a[j]), value=(i = 0, j = 1) à la file d'attente de priorité.
2. Pop (sum, i, j) à partir de la priorité de la file d'attente.
3. utilisez sum dans l'algorithme ci-dessus.
4. mettre (a[i+1] + a[j]), i+1, j et (a[i] + a[j+1]), i, j+1 en file d'attente prioritaire uniquement si ces éléments n'étaient pas déjà utilisés. Pour garder la trace des éléments utilisés, maintenez un tableau de maximal utilisé 'j' pour chaque 'i'. Il suffit d'utiliser seulement les valeurs de 'j', qui sont plus, que "je".
5. continuez de l'étape 2.

Pour k>4

si la complexité de l'espace est limitée à O (n), Je ne peux rien trouver de mieux que d'utiliser la force brute pour les valeurs k-4 et l'algorithme ci-dessus pour les autres valeurs 4 . Complexité temporelle O (N ^(k-2) * log (n)).

Pour les très grandes k integer linear programming peut donner une certaine amélioration.

mise à Jour

si n est très grand (sur le même ordre que la valeur entière maximale), il est possible de mettre en œuvre O(1) file d'attente prioritaire, en améliorant les complexités à O(N ² ) et O(N ^(k-2) ).

Si n >= k * INT_MAX , différent de l'algorithme à temps O(n) l'espace de la complexité est possible. Précalculer un bitset pour toutes les sommes possibles de valeurs k/2 . Et l'utiliser pour vérifier les sommes d'autres valeurs k/2 . Temps la complexité est O (N ^{(ceil (k/2))} ).

le problème de déterminer si 0 en W + X + Y + Z = {w + x + y + z | w en W, x en X, y en Y, z en Z} est fondamentalement le même sauf pour ne pas avoir de cas dégénérés ennuyeux (c.-à-d., les problèmes sont inter-réductibles avec des ressources minimales).

ce problème(et donc l'original pour k = 4) a un algorithme O(N^2 log n)-time, O (n)-space. L'algorithme O (N log n)-time pour k = 2 (pour déterminer si 0 en A + B) accède A en ordre trié et B en ordre inverse l'ordre de tri. Ainsi, tout ce dont nous avons besoin est un itérateur O(n)-space pour A = W + X, qui peut être réutilisé symétriquement pour B = Y + Z. Let W = {w1,..., wn} dans l'ordre de tri. Pour tous les x dans X, insérez un élément clé-valeur (w1 + x, (1, x)) dans une file d'attente prioritaire. Supprimer à plusieurs reprises l'élément min (wi + x, (i, x)) et insérer (wi+1 + x, (i+1, x)).

Question qui est très similaire:

est-ce que cette variante du problème de la somme des sous-ensembles est plus facile à résoudre?

c'est toujours NP-complet.

si ce n'était pas le cas, le sous-ensemble-somme serait aussi en P, car il pourrait être représenté comme F(1) | F(2) | ... F(n) où F est votre fonction. Cela aurait O(O(F(1)) + O(F(2)) + O(F(n))) qui serait encore polynomial, ce qui est incorrect car nous savons qu'il est NP-complet.

Note que si vous avez certaines limites sur les entrées vous pouvez obtenir des temps polynomial.

notez aussi que la durée de la force brute peut être calculée avec des coefficients binomiaux.

La solution pour k=4 en O(n^2log(n))

Étape 1: calculer la somme en paires et trier la liste. Il y a n (n-1)/2 sommes. Donc la complexité est O (N^2log (n)). Gardez l'identité des individus qui font la somme.

Étape 2: pour chaque élément de la liste ci-dessus, cherchez le complément et assurez-vous qu'ils ne partagent pas "les individus". Il y a n^2 recherches, chacune avec une complexité O(log (n))

EDIT: la complexité spatiale de l'algorithme original est O(N^2). La complexité de l'espace peut être réduite à O(1) en simulant une matrice 2D virtuelle (O(n), Si vous considérez l'espace pour stocker la version triée du tableau).

d'abord une matrice 2D: trier les nombres et créer une matrice X en utilisant des sommes en paires. Maintenant la matrice est telle que toutes les lignes et les colonnes sont triées. Pour rechercher une valeur dans cette matrice, recherche les numéros sur la diagonale. Si le nombre est entre X[i,i] et X[i+1,i+1], vous pouvez réduire de moitié l'espace de recherche par des matrices X[i:N, 0:i] et X[0:i, i:N]. L'algorithme de recherche qui en résulte est O(log^2n) (Je ne suis pas très sûr. QUELQU'UN PEUT-IL VÉRIFIER?).

maintenant, au lieu d'utiliser une matrice réelle, utilisez une matrice virtuelle où X[i,j] sont calculés au besoin au lieu de les pré-calculer.

Résultant du temps de la complexité: O (nlogn)^2 ).

PS: dans le lien suivant, il est dit la complexité de la recherche matricielle 2D triée est O (n) complexité. Si cela est vrai (i.e. O (log^2n) est incorrect), alors la complexité finale est O(N^3).

la complexité temporelle est trivialement O(n^k) (nombre de sous-ensembles de la taille de k de n éléments).

étant donné que k est une constante donnée, un polynôme supérieur (peut-être d'ordre très élevé) limite la complexité en fonction de n .

pour construire sur la réponse d'awesomo... si nous pouvons supposer que les nombres sont triés, nous pouvons faire mieux que O(N^k) pour un k donné; il suffit de prendre tous les sous-ensembles O(N^(k-1)) de taille (k-1), puis faire une recherche binaire dans ce qui reste pour un nombre qui, une fois ajouté à la première (k-1), donne la cible. C'est O(N^(k-1) log n). Cela signifie que la complexité est certainement moins que cela.

en fait, si nous savons que la complexité est O (N^2) pour k=3, Nous pouvons faire encore mieux pour k > 3: Choisissez tous (k-3)-sous-ensembles, dont il existe O(N^(k-3)), puis résoudre le problème en O(N^2) sur les éléments restants. C'est O(N^(k-1)) pour k >= 3.

cependant, peut-être Pouvez-vous faire encore mieux? Je vais réfléchir".

EDIT: j'allais ajouter un lot en proposant une approche différente de ce problème, mais j'ai décidé de poster une version abrégée. J'encourage les autres posters à voir s'ils croient que cette idée a du Mérite. L'analyse est difficile, mais il pourrait juste être assez fou pour travailler.

nous pouvons utiliser le fait que nous avons un K fixe, et que les sommes de nombres impairs et pairs se comportent d'une certaine manière, pour définir un algorithme récursif pour résoudre ce problème.

tout D'abord, modifiez le problème de sorte que vous ayez les nombres pairs et impairs dans la liste (ceci peut être accompli en divisant par deux si tous sont pairs, ou en soustrayant 1 des nombres et k de la somme cible si tous sont impairs, et en répétant comme suit: nécessaire.)

ensuite, utilisez le fait que même les sommes cibles ne peuvent être atteintes qu'en utilisant un nombre pair de nombres impairs, et les sommes cibles impairs peuvent être atteintes en utilisant seulement un nombre impair de nombres impairs. Générer des sous-ensembles de nombres impairs, et d'appeler l'algorithme récursivement en utilisant le même nombre, la somme, moins la somme des sous-ensemble des nombres impairs examiné, et k moins la taille du sous-ensemble des nombres impairs. Quand k = 1, Faites une recherche binaire. Si jamais k > n (Pas sûr cela peut arriver), renvoie false.

si vous avez très peu de nombres impairs, cela pourrait vous permettre de saisir très rapidement les termes qui doivent faire partie d'un sous-ensemble gagnant, ou d'écarter ceux qui ne peuvent pas. Vous pouvez transformer des problèmes avec beaucoup de nombres pairs en problèmes équivalents avec beaucoup de nombres impairs en utilisant le truc de soustraction. Le cas le plus défavorable doit donc être celui où les nombres pairs et impairs sont très semblables... et c'est là où je suis maintenant. Un haut inutilement lâche il y a beaucoup d'ordres de grandeur pires que la force brute, mais j'ai l'impression que c'est probablement au moins aussi bon que la force brute. Les pensées sont les bienvenues!

EDIT2: un exemple de ce qui précède, pour illustration.

{1, 2, 2, 6, 7, 7, 20}, k = 3, sum = 20.
Subset {}:
 {2, 2, 6, 20}, k = 3, sum = 20
 = {1, 1, 3, 10}, k = 3, sum = 10
 Subset {}:
  {10}, k = 3, sum = 10
  Failure
 Subset {1, 1}:
  {10}, k = 1, sum = 8
  Failure
 Subset {1, 3}:
  {10}, k = 1, sum = 6
  Failure
Subset {1, 7}:
 {2, 2, 6, 20}, k = 1, sum = 12
 Failure
Subset {7, 7}:
 {2, 2, 6, 20}, k = 1, sum = 6
 Success