Algoritmo per trovare un sottoinsieme all'interno di due serie di numeri interi le cui somme corrispondono

Question

Sto cercando un algoritmo che può prendere due serie di numeri interi (sia positivi che negativi) e trovare sottoinsiemi all'interno di ciascuno che abbiano la stessa somma.

Il problema è simile al problema del sottoinsieme di somme tranne che sto cercando per sottoinsiemi su entrambi i lati.

Ecco un esempio:

Elenco A {4, 5, 9, 10, 1}

Elenco B {21, 7, -4, 180}

Quindi l'unica corrispondenza qui è: {10, 1, 4, 9} & Lt; = & Gt; {21, 7, -4}

Qualcuno sa se ci sono algoritmi esistenti per questo tipo di problemi?

Finora, l'unica soluzione che ho è un approccio di forza bruta che prova ogni combinazione ma si comporta in tempo esponenziale e ho dovuto mettere un limite duro al numero di elementi da considerare per evitare che impiegasse troppo tempo .

L'unica altra soluzione che mi viene in mente è quella di eseguire un fattoriale su entrambi gli elenchi e cercare le uguaglianze lì, ma ciò non è ancora molto efficiente e richiede esponenzialmente più tempo man mano che le liste diventano più grandi.

Answer 1

Ciò che altri hanno detto è vero:

1. Questo problema è NP-completo. Una facile riduzione è alla solita somma dei sottoinsiemi. Puoi mostrarlo osservando che un sottoinsieme di A si somma a un sottoinsieme di B (non entrambi vuoti) solo se un sottoinsieme non vuoto di una unione (-B) si somma a zero.

2. Questo problema è solo debolmente completo di NP, in quanto è polinomiale nella dimensione dei numeri coinvolti, ma è ipotizzato esponenziale nei loro logaritmi . Ciò significa che il problema è più semplice rispetto al moniker & Quot; NP-complete & Quot; potrebbe suggerire.

3. Dovresti usare la programmazione dinamica.

Quindi, a cosa sto contribuendo a questa discussione? Bene, codice (in Perl):

@a = qw(4 5 9 10 1);
@b = qw(21 7 -4 180);
%a = sums( @a );
%b = sums( @b );
for $m ( keys %a ) {
    next unless exists $b{$m};
    next if $m == 0 and (@{$a{0}} == 0 or @{$b{0}} == 0);
    print "sum(@{$a{$m}}) = sum(@{$b{$m}})\n";
}

sub sums {
    my( @a ) = @_;
    my( $a, %a, %b );
    %a = ( 0 => [] );
    while( @a ) {
        %b = %a;
        $a = shift @a;
        for my $m ( keys %a ) {
            $b{$m+$a} = [@{$a{$m}},$a];
        }
    %a = %b;
    }
    return %a;
}

Stampa

sum(4 5 9 10) = sum(21 7)
sum(4 9 10 1) = sum(21 7 -4)

quindi, in particolare, esiste più di una soluzione che funziona nel tuo problema originale!

Modifica : l'utente itzy ha correttamente sottolineato che questa soluzione era sbagliata e, peggio ancora, in più modi !! Mi dispiace molto per questo e spero di aver affrontato queste preoccupazioni nel nuovo codice sopra. Tuttavia, c'è ancora un problema, vale a dire che per ogni particolare sottoinsieme, stampa solo una delle possibili soluzioni. A differenza dei problemi precedenti, che erano errori diretti, lo classificherei come una limitazione intenzionale. Buona fortuna e attenzione ai bug!

Answer 2

Come il problema della somma dei sottoinsiemi, questo problema è debolmente NP-completo, quindi ha una soluzione che gira nel polinomio temporale (M), dove M è la somma di tutti i numeri che compaiono nel problema esempio. Puoi farlo con la programmazione dinamica. Per ogni set è possibile generare tutte le possibili somme compilando una tabella binaria bidimensionale, dove & Quot; true & Quot; at (k, m) significa che una somma di sottoinsieme m può essere ottenuta selezionando alcuni elementi dai primi k elementi dell'insieme.

Lo riempi iterativamente - imposti (k, m) su " true " se (k-1, m) è impostato su " vero " (ovviamente, se puoi ottenere m da k-1 elementi, puoi ottenerlo da k elementi non selezionando il k-esimo) o se (k-1, md) è impostato su " true " dove d è il valore dell'elemento k-esima nell'insieme (il caso in cui si sceglie l'elemento k-esima).

Riempiendo la tabella ottieni tutte le somme possibili nell'ultima colonna (quella che rappresenta l'intero set). Fallo per entrambi i set e trova somme comuni. Puoi tornare indietro ai sottoinsiemi reali che rappresentano le soluzioni invertendo il processo che hai usato per riempire le tabelle.

Answer 3

Grazie mille per tutte le risposte rapide!

La soluzione di programmazione dinamica non è molto diversa dall'approvazione esaustiva che abbiamo in questo momento e immagino che se abbiamo bisogno della soluzione ottimale dobbiamo prendere in considerazione ogni possibile combinazione, ma anche il tempo necessario per generare questo elenco esaustivo di somme lungo.. Ha effettuato un test rapido e il tempo necessario per generare tutte le possibili somme per x numero di elementi molto rapidamente supera 1 minuto:

11 elements took - 0.015625 seconds
12 elements took - 0.015625 seconds
13 elements took - 0.046875 seconds
14 elements took - 0.109375 seconds
15 elements took - 0.171875 seconds
16 elements took - 0.359375 seconds
17 elements took - 0.765625 seconds
18 elements took - 1.609375 seconds
19 elements took - 3.40625 seconds
20 elements took - 7.15625 seconds
21 elements took - 14.96875 seconds
22 elements took - 31.40625 seconds
23 elements took - 65.875 seconds
24 elements took - 135.953125 seconds
25 elements took - 282.015625 seconds
26 elements took - 586.140625 seconds
27 elements took - 1250.421875 seconds
28 elements took - 2552.53125 seconds
29 elements took - 5264.34375 seconds

quale per il problema aziendale che stiamo cercando di risolvere non è davvero accettabile. Tornerò al tavolo da disegno e vedremo se abbiamo davvero bisogno di conoscere tutte le soluzioni o possiamo semplicemente fare con uno ( il sottoinsieme più piccolo / più grande, ad es.) invece, e si spera, che possa aiutare semplicemente il problema e far funzionare il mio algoritmo in modo eccezionale.

Grazie lo stesso!

Answer 4

la somma del sottoinsieme è Np-completa e puoi ridurre polinomialmente il tuo problema ad esso, quindi anche il tuo problema è NP-completo.