Como perceber aplicável meet-in-the-middle algoritmo da Mochila 0-1?

Question

Agora estou estudando a Mochila Problema (PQ), e encontrar o Meet-in-the-middle algoritmo descrito em Taxas um pouco claro que, como realizá-lo no campo teórico, tempo de complexidade $S^*(2^{n/2})$?Eu posso entender o algoritmo para Soma dos Subconjuntos Problema (SSP), que é uma instância específica de 0-1 PQ, mas para o tipo de problema que pode haver algo errado com o passo:

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

Como eu entendo, isso é pesquisa (ex.fazer pesquisa binária) na combinação de pesos de todos os subconjuntos de B, o que leva o logaritmo do tempo para cada pesquisa.Mas depois de saber que subconjuntos de ter combinado com peso inferior a W, como encontrar aquele de maior valor?Se a pesquisa sobre os valores dos subconjuntos com peso < W, leva tempo linear para encontrar o máximo desde que a lista de valor não ordenada neste momento.Como resultado, o tempo total de complexidade não é mais $S^*(2^{n/2})$, mas algo como $S^*(2^n)$.

Mesmo se ele começa a partir de encontrar o subconjunto de maior valor (o que é fácil para uma tabela) primeiro sem constrição em peso combinado, após o que, verificação de peso, provavelmente irá virar falso e, portanto, são necessários mais testes para outros subconjuntos, de que o número parece associado à tabela de tamanho linearmente novamente.

Agora eu só posso supor que o valor total e peso combinado são fortemente positivos correlacionados, de modo que depois de encontrar o subconjunto com o máximo de peso permitido, leva apenas a constante de tempo para a pesquisa em torno deste subconjunto para um exato de maior valor.Mas eu não estou satisfeito com essa explicação.Assim, alguém tem idéia melhor sobre esta questão?

PS:Eu li o original em papel por Horowitz, Ellis e Sahni, Sartaj, mas achei que o problema definido há um problema de decisão, ao invés do que o comum problema de otimização.Talvez alguém pode fornecer ideias neste sentido.

Answer 1

Primeiro, precompute os pesos de cada subconjunto de $B$.

Ordená-los por peso e colocar os pesos e subconjuntos em paralelo matrizes, de modo a que $W[i] = peso$ e $S[i] = subconjunto$.

Em seguida, fazer outra matriz paralela, de modo que $BEST[i]$ é o índice de $j$ do conjunto de maior valor tal que $j<=i$.Você pode fazer isso com um único exame de $i=0$ para cima, lembrando-se do maior valor de visto até agora a cada passo.

Agora, a pesquisa $B$, você fazer uma pesquisa binária em $W$ para encontrar o valor máximo admissível de peso, e obter o melhor conjunto do mesmo índice em $MELHOR$