Sum-sottoinsieme con un sottoinsieme fisso

Question

I sum-subset problem paese:

Dato un insieme di numeri interi, c'è un sottoinsieme non vuoto la cui somma è pari a zero?

Questo problema è NP-completo in generale. Sono curioso di sapere se la complessità di questa leggera variante è nota:

Dato un insieme di numeri interi, v'è un sottoinsieme del formato k la cui somma è pari a zero?

Ad esempio, se k = 1, è possibile eseguire una ricerca binaria per trovare la risposta in O(log n). Se k = 2, è possibile scaricarlo a O(n log n) (ad esempio, vedere Find a pair of elements from an array whose sum equals a given number). Se k = 3, è possibile eseguire O(n^2) (ad esempio, vedere Finding three elements in an array whose sum is closest to a given number).

Esiste un noto bound che può essere posizionato su questo problema come una funzione di k?

come motivazione, stavo pensando a questa domanda How do you partition an array into 2 parts such that the two parts have equal average? e cercando di determinare se in realtà è NP-completo. La risposta sta nel fatto che ci sia o meno una formula come descritto sopra.

Salvo una soluzione generale, sarei molto interessato a conoscere un limite ottimale per k=4.

Answer 1

La complessità del tempo è banalmente O(n^k) (numero di sottoinsiemi dimensionati da n elementi).

Poiché k è una costante determinata, un limite superiore polinomiale (possibilmente piuttosto elevato) compensa la complessità in funzione di n.

Answer 2

domanda che è molto simile:

Is this variant of the subset sum problem easier to solve?

E 'ancora NP-completo.

In caso contrario, la sottoinsieme sarebbe anche in P, in quanto potrebbe essere rappresentato come F(1) | F(2) | ... F(n) dove F è la vostra funzione. Questo avrebbe O(O(F(1)) + O(F(2)) + O(F(n))) che sarebbe ancora polinomiale, che non è corretto in quanto sappiamo che è NP-completo.

Si noti che se si dispone di determinati limiti sugli ingressi è possibile ottenere il tempo polinomiale.

Si noti inoltre che il runtime forza bruta può essere calcolato con coefficienti binomiali.

Answer 3

Per costruire la risposta di awesomo ... se possiamo assumere che i numeri siano ordinati, possiamo fare meglio di O (n^k) per dato k; semplicemente prendi tutti i sottoinsiemi di dimensione O (n^(k-1)) (k-1), poi fai una ricerca binaria in quello che rimane per un numero che, aggiunto al primo (k-1), dà il bersaglio. Questo è O (n^(k-1) log n). Ciò significa che la complessità è certamente inferiore a quella.

Infatti, se sappiamo che la complessità è O (n^2) per k = 3, possiamo fare ancora meglio per k> 3: scegliere tutti i sottotitoli (k-3), di cui ci sono O (n^(k-3)), quindi risolvi il problema in O (n^2) sugli altri elementi. Questo è O (n^(k-1)) per k> = 3.

Tuttavia, forse si può fare anche meglio? Ci penserò su questo.

EDIT: Inizialmente aggiungevo un sacco di proposte su un problema diverso, ma ho deciso di pubblicare una versione ridotta. Incoraggio altri poster a vedere se credono che questa idea abbia qualche merito. L'analisi è dura, ma potrebbe essere abbastanza folle da funzionare.

Possiamo usare il fatto che abbiamo un k fisso e che le somme di numeri pari e dispari si comportano in certi modi, per definire un algoritmo ricorsivo per risolvere questo problema.

In primo luogo, modificare il problema in modo che si disponga di entrambi i numeri pari e dispari nell'elenco (questo può essere ottenuto dividendo per due se tutti sono pari, o sottraendo 1 da numeri ek dalla somma di destinazione se tutti sono dispari e ripetuti se necessario).

Successivamente, utilizzare il fatto che è possibile raggiungere anche somme di destinazione solo utilizzando un numero pari di numeri dispari, e le somme di destinazione dispari possono essere raggiunte utilizzando solo un numero dispari di numeri dispari. Generare sottoinsiemi appropriati dei numeri dispari e chiamare l'algoritmo in modo ricorsivo usando i numeri pari, la somma meno la somma del sottoinsieme di numeri dispari esaminati, e k meno la dimensione del sottoinsieme di numeri dispari. Quando k = 1, fai una ricerca binaria. Se mai k> n (non è sicuro che ciò possa accadere), restituisci falso.

Se si dispone di pochissimi numeri dispari, questo potrebbe consentire di acquisire rapidamente termini che devono far parte di un sottoinsieme vincente o scartare quelli che non possono. Puoi trasformare i problemi con molti numeri pari in problemi equivalenti con molti numeri dispari usando il trucco di sottrazione. Il caso peggiore deve quindi essere quando il numero di numeri pari e dispari è molto simile ... ed è qui che mi trovo in questo momento. Un limite superiore inutilmente allentato su questo è un numero di ordini di magnitudo peggiore di quello della forza bruta, ma credo che questo sia probabilmente almeno buono quanto la forza bruta. I pensieri sono ben accetti!

EDIT2: un esempio di quanto sopra, per illustrazione.

{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 

Answer 4

La soluzione per k = 4 a O (n^2log (n))

Passo 1: Calcolare la somma coppie e ordinare l'elenco. Ci sono n (n-1)/2 somme. Quindi la complessità è O (n^2log (n)). Mantieni le identità degli individui che fanno la somma.

Fase 2:. Per ogni elemento nella ricerca lista qui sopra per il complemento e assicurarsi che essi non condividono "gli individui) Ci sono n^2 ricerche, ciascuna con la complessità O (log (n))

MODIFICA: La complessità spaziale dell'algoritmo originale è O (n^2). La complessità dello spazio può essere ridotta a O (1) simulando una matrice 2D virtuale (O (n), se si considera lo spazio per memorizzare la versione ordinata dell'array)

Prima sulla matrice 2D: ordina i numeri e crea una matrice X utilizzando le somme pairwise Ora la matrice è in modo tale che tutte le righe e le colonne siano ordinate. matrice, cercare i numeri sulla diagonale.Se il numero è i n tra X [i, i] e X [i + 1, i + 1], puoi praticamente dimezzare lo spazio di ricerca di matrici X [i: N, 0: i] e X [0: i, i: N ]. L'algoritmo di ricerca risultante è O (log^2n) (NON SONO MOLTO SICURO. POSSO QUALCUNO VERIFICARLO?).

Ora, invece di utilizzare una matrice reale, utilizzare una matrice virtuale in cui X [i, j] vengono calcolati come necessario invece di pre-calcolarli.

Complessità temporale risultante: O ((nlogn)^2).

PS: Nel seguente collegamento, si dice che la complessità della ricerca di matrice ordinata 2D è O (n) complessità. Se ciò è vero (cioè O (log^2n) non è corretto), allora la complessità finale è O (n^3).

Answer 5

Il problema di determinare se 0 in W + X + Y + Z = {w + x + y + z | w in W, x in X, y in Y, z in Z} è fondamentalmente lo stesso eccetto per non avere fastidiosi casi degenerati (cioè, i problemi sono interdiducibili con risorse minime).

Questo problema (e quindi l'originale per k = 4) ha un algoritmo O (n^2 log n) -time, O (n) -space. L'algoritmo O (n log n) per k = 2 (per determinare se 0 in A + B) accede A in ordine ordinato e B in ordine inverso. Quindi tutto ciò di cui abbiamo bisogno è un iteratore di spazio O (n) per A = W + X, che può essere riutilizzato simmetricamente per B = Y + Z. Sia W = {w1, ..., wn} in ordine. Per tutti x in X, inserisci un elemento valore-chiave (w1 + x, (1, x)) in una coda di priorità. Rimuovere ripetutamente l'elemento min (wi + x, (i, x)) e inserire (wi + 1 + x, (i + 1, x)).

Answer 6

Per k = 4, spazio complessità O (n), tempo di complessità O (n * log (n))

ordine dell'array. A partire da 2 elementi più piccoli e 2 più grandi, calcolare tutti gli lesser somme di 2 elementi (a[i] + a[j]) nell'ordine decrescente e tutte le somme da greater di 2 elementi (a[k] + a[l]) nell'ordine non crescente. Aumentare la somma lesser se la somma totale è inferiore a zero, diminuire greater uno se la somma totale è maggiore di zero, interrompere quando la somma totale è zero (esito positivo) o a[i] + a[j] > a[k] + a[l] (errore).

Il trucco è di scorrere tutti gli indici i e j in modo tale che (a[i] + a[j]) non diminuirà mai. E per k e l, (a[k] + a[l]) non dovrebbe mai aumentare. Una coda di priorità aiuta a fare questo:

1. Mettere key=(a[i] + a[j]), value=(i = 0, j = 1) alla coda di priorità.
2. Pop (sum, i, j) dalla coda di priorità.
3. Utilizzare sum nell'algoritmo di cui sopra.
4. Inserire (a[i+1] + a[j]), i+1, j e (a[i] + a[j+1]), i, j+1 nella coda di priorità solo se questi elementi non erano già utilizzati. Per tenere traccia degli elementi usati, mantieni una matrice di massima 'j' usata per ogni 'i'. È sufficiente utilizzare solo i valori per "j", che sono maggiori di "i".
5. Continuare dal passaggio 2.

Per k> 4

Se complessità spaziale è limitato a O (n), non riesco a trovare niente di meglio, di usare la forza bruta per k-4 valori e il algoritmo di cui sopra per i restanti valori 4. Complessità temporale O (n ^(k-2) * log (n)).

Per molto grandi kinteger linear programming può dare qualche miglioramento.

Aggiorna

Se n è molto grande (sullo stesso ordine come valore massimo intero), è possibile implementare O (1) coda di priorità, migliorando complessità a O (n) e O (n ^(k-2)).

Se n >= k * INT_MAX, è possibile un diverso algoritmo con O (n). Calcolare un set di bit per tutte le possibili somme dei valori k/2. E usalo per controllare somme di altri valori k/2. La complessità temporale è O (n. ^{(ceil (k/2))}).