Come realizzare l'algoritmo medio-in-the-medio applicabile per 0-1 zaino?

Question

Ora sto studiando il problema dello zaino (KP) e trova l'algoritmo incontro-in-the-medio descritto in wikipedia un po 'poco chiara che, come rendersi conto nella complessità del tempo teorico della $ o ^ * (2 ^ {n / 2}) $ ? Posso capire l'algoritmo per il problema del sottoinsieme del problema (SSP) che è un'istanza particolare di 0-1 kP, ma per il problema generalizzato potrebbe esserci qualcosa di sbagliato nel passaggio:

.

  for each subset of A do
      find the subset of B of greatest value such that the combined weight is less than W

.

Come ho capito, questo è quello di cercare (ad esempio Ricerca binaria) sui pesi combinati di tutti i sottoinsiemi di B, che prende il tempo di logaritmo per ogni ricerca. Ma dopo sapere quali sottoinsiemi hanno combinato peso inferiore a W, come trovare quello del più grande valore? Se cerca i valori dei sottoinsiemi con il peso $ o ^ * (2 ^ {n / 2}) $ , ma qualcosa come $ O ^ * (2 ^ N) $ .

Anche se inizia a trovare il sottoinsieme del più grande valore (facile per una tabella) prima senza costrizione sul peso combinato, dopo di ciò, la verifica del peso diventerà probabilmente falsa e quindi più test sono necessari per altri sottoinsiemi, di cui il Il numero sembra associato alla dimensione della tabella linearmente di nuovo.

Ora posso supporre solo il valore totale e il peso combinato sono fortemente correlati positivi, in modo che dopo aver trovato il sottoinsieme con il peso massimo consentito, ci vuole solo il tempo costante per cercare attorno a questo sottoinsieme per l'esatto valore del più grande valore. Ma non sono soddisfatto di questa spiegazione. Quindi chiunque abbia idee migliori su questo problema?

PS: Ho letto la carta originale di Horowitz, Ellis e Sahni, Sartaj, ma ho trovato il problema definito che c'è un problema decisionale piuttosto che il problema di ottimizzazione comune. Forse qualcuno può fornire idee in questa direzione.

Answer 1

In primo luogo, preputa i pesi di ogni sottoinsieme di $ B $ .

Ordinali in peso e inserire i pesi e le sottostime in array paralleli in modo che $ w w [i]= peso $ e $ S [i]= sottoinsieme $ .

Quindi crea un altro array parallelo in modo che $ miglior [i] $ è l'indice $ j $ del set di più grande valore tale che $ j <= I $ .Puoi farlo con una singola scansione da $ i= 0 $ verso l'alto, ricordando il massimo valore visto fino ad ogni passo.

Ora, per cercare $ B $ , fai una ricerca binaria in $ W $ per trovareIl peso massimo consentito e ottieni il set migliore dallo stesso indice in $ miglior $