È questa variante del problema sottoinsieme somma più facile da risolvere?

StackOverflow https://stackoverflow.com/questions/376003

Domanda

Ho un problema relativo alla sottoinsieme somma problema e mi chiedo se le differenze rendono più facile, cioè risolvibile in un ragionevole lasso di tempo.

Dato un valore V, una dimensione impostata L, e una sequenza di numeri [1, N] S, quanti sottoinsiemi di somma S a meno di V? Misura L

Questo è diverso rispetto al problema sottoinsieme somma in tre modi:

  1. mi importa quanti sottoinsiemi sono meno di un determinato valore, non quanti sono uguale .
  2. Le dimensioni di sottoinsieme sono fissi.
  3. mi interessa il numero imposta somma inferiore a V, non solo se ne esistono.

Esiste un algoritmo ragionevolmente efficiente per risolvere questo?

Modifica: Ovviamente, questo può essere fatto in O (N scegliere L) utilizzando una combinazione genera algoritmo. Quello che mi interessa veramente è hack intelligenti per accelerare in modo significativo fino passato.

È stato utile?

Soluzione

(La versione di decisione) il problema è ancora NP-completo. L'idea è che se si potesse risolvere il tuo problema, allora (per ogni dimensione sottoinsieme, per esempio) potremmo chiedere quanti set sommano a meno di V e quanti somma a meno di V-1, e la differenza di questi due numeri saremmo dirci se sono sottoinsiemi che somma esattamente V - così si potrebbe risolvere il problema sottoinsieme somma. [Questa non è una prova completa, perché è un Turing riduzione, non un molti una riduzione .]

Tuttavia, v'è un soluzione semplice programmazione dinamica che viene eseguito in tempo O (NLV). [La ragione ciò non prova che P = NP è che V potrebbe essere esponenziale nella dimensione ingresso: con n bit, è possibile rappresentare valori fino a 2 n . Ma supponendo che il vostro V non è esponenziale, questo non è un problema.]

Sia num [v] [k] [i] denota il numero di sottoinsiemi size-k dei primi elementi i di S tale somma a v È possibile calcolare come (per ogni i):. 

    num[0][0][i] = 1
    for v = 1 to V:
        for k = 1 to L:
            num[v][k][i] = num[v][k][i-1] + num[v-S[i]][k-1][i-1]

dove S [i] è l'elemento-esimo nella sequenza. (Qualsiasi insieme di k dimensioni che somma a v o non usa S [i], quindi è conteggiato in num [v] [k] [i-1], o utilizza S [i], che significa che il resto il sottoinsieme ha k elementi-1, utilizza i numeri solo il primo i-1 nella sequenza, e somme vs [i]) Infine, conteggio num [v] [L]. [| S |] per ogni v meno di v ; questa è la vostra risposta.

Inoltre, è possibile omettere il terzo indice, se lo si fa con attenzione (eseguire il ciclo verso il basso per ogni i, etc.); Ho incluso solo per chiarezza.

Altri suggerimenti

Io non sono disposti a presentare una prova, ma che suona come potrebbe essere suscettibile di uno schema di programmazione dinamica: tabulare l'elenco dei sottoinsiemi di dimensioni li 2Utilizzare per sottoinsiemi di computer di dimensioni 3, ecc, in modo che solo bisogno hyou per esaminare una piccola collezione di prospettive.

Un'ottimizzazione che viene in mente è questo: Ordinare la sequenza (se alerady non è così). Scegli i primi L-1 elementi dall'inizio di esso, e poi scegliere l'ultimo elemento ad esempio, che è il più grande valore possibile (il prossimo valore più grande nella sequenza darebbe una somma troppo grande). Scartare il resto della sequenza, in quanto tali elementi non possono mai essere una parte di un sottoinsieme valida in ogni caso.

Dopo di che credo che sia la ricerca di nuovo piena. Ma poi di nuovo ci potrebbero essere possibili altre optimiziations troppo.

La soluzione di programmazione dinamica al problema sottoinsieme somma genera una tabella che contiene questa risposta (cioè una tabella booleana di V di N dove V è il numero massimo di elementi e N è il numero massimo di elementi che possono essere in un set che satisifies i vincoli, ciascuna boolean essere vero se <= N elementi sommano a <= V). Quindi, se N * V non è troppo grande per te, esiste un algoritmo accettabilmente veloce. La soluzione sottoinsieme somma è solo l'elemento più alto impostato in questa tabella per cui il numero di elementi è <= N / 2.

Se è solo numeri interi positivi, si può fare una fase di verifica se avete bisogno ;

Fate il conto dei più piccoli interi L-1 nel set. Se questo è una somma X, allora n-X deve essere sotto l'elemento più grande se il problema è dovrebbe per avere una soluzione. Vieni a pensarci bene, è possibile eliminare altri L questo modo ...

Beh, per prima cosa dal momento che stai specificando size = L allora anche se non si può pensare a qualcosa di intelligente e basta usare la forza bruta avrete (N scegliere L) somme separate nel caso peggiore, quindi è un po 'meglio di n ^^ L (beh, L + 1, come ci si poi sommare ogni sottoinsieme).

Questo suona come una categoria k n scegliere di problema. Generazione di k-sottoinsiemi di n è coperto nel Manuale Algoritmo design di Skiena, e il libro suggerisce enumerare sottoinsiemi rilevanti in ordine lessicografico (in modo ricorsivo, per esempio). Poi fate la vostra somma e confronto su ogni sottoinsieme.

Se si dispone di un insieme ordinato, si potrebbe presumibilmente potare soluzioni impossibili dallo spazio delle soluzioni.

Forse la formulazione programmazione dinamica è amenamble ad un PTAS di FPTAS.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top