¿Cómo realizar un algoritmo de reunión aplicable para 0-1 Knapsack?

Question

Ahora estoy estudiando un problema de mochila (KP) y encuentre el algoritmo de reunión en el medio descrito en wikipedia un poco no claro que, cómo realizarlo en la complejidad de tiempo teórico de $ o ^ * (2 ^ {n / 2}) $ ? Puedo entender el algoritmo para el problema de suma de subconjunto (SSP), que es una instancia particular de 0-1 kp, pero para el problema generalizado podría haber algo malo con el paso:

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

Como entiendo, esto es para buscar (por ejemplo, hacer una búsqueda binaria) en pesos combinados de todos los subconjuntos de B, que lleva el tiempo de logaritmo para cada búsqueda. Pero, después de saber, ¿qué subconjuntos han combinado peso menor que W, cómo encontrar el de mayor valor? Si se busca en los valores de los subconjuntos con peso $ o ^ * (2 ^ {n / 2}) $ , pero algo como $ o ^ * (2 ^ n) $ .

Incluso si comienza a encontrar el subconjunto de mayor valor (fácil para una tabla) primero sin constricción en peso combinado, después de eso, la verificación del peso probablemente se convertirá en falso y, por lo tanto, se necesitan más pruebas para otros subconjuntos, de los cuales el El número parece asociado al tamaño de la tabla linealmente de nuevo.

Ahora, solo puedo asumir que el valor total y el peso combinado están fuertemente positivos correlacionados, de modo que después de encontrar el subconjunto con el peso máximo permitido, solo toma tiempo constante para buscar en este subconjunto para el mayor valor más grande. Pero no estoy satisfecho con esta explicación. ¿Alguien tiene mejores ideas sobre este tema?

PS: He leído el papel original de Horowitz, Ellis y Sahni, Sartej, pero encontré el problema definido, existe un problema de decisión en lugar del problema de optimización común. Tal vez alguien pueda proporcionar ideas en esta dirección.

Answer 1

Primero, precomputa los pesos de cada subconjunto de $ b $ .

Ordenarlos en peso y colocar los pesos y subconjuntos en matrices paralelas para que $ w [i]= peso $ y $ S [i]= subconjunto $ .

Luego, haga otra matriz paralela para que $ Best [i] $ es el índice $ j $ del conjunto de mayor valor de modo que $ j <= i $ .Puede hacerlo con una sola exploración de $ i= 0 $ hacia arriba, recordando el mayor valor visto hasta ahora en cada paso.

Ahora, para buscar $ b $ , realiza una búsqueda binaria en $ w $ para encontrarEl peso máximo permisible, y obtenga el mejor juego del mismo índice en $ mejor $