Resuelve el problema de mochila 0-1 en línea de 0-1 de manera eficiente

Question

Tengo $ n $ artículos y un contenedor de tamaño $ b $ unidades. Cada artículo $ j $ consume $ w_j $ unidades de $ B $ cuando se coloca en la mochila. El artículo aparece uno por uno en una moda en línea. Una vez que aparece el artículo $ i $ , debemos colocarlo en la papelera (irrevocablemente) o ignorarlo. El objetivo es maximizar el número de elementos colocados en el contenedor. (Todas las entradas son enteros positivos.)

El algoritmo sin conexión es fácil: coloque los elementos en el pedido $ w_1 \ leq w_2 \ leq \ cdots \ leq w_n $ hasta que la papelera esté llena.

¿Cómo puedo resolver este problema en una moda en línea? Mi enfoque es aleatorizar las opciones: una vez que aparece el artículo $ j $ , colóquelo en la bandeja con probabilidad $ p_j $ < / SPAN> e ignóralo de lo contrario.

Answer 1

Bueno, como ya se notó, o al menos no mencionó, es fácil ver que no hay un algoritmo competitivo determinista para su problema.(Los contraexamplos solo necesitan dos elementos, y puede usar el hecho de que el algoritmo es determinista).

Su enfoque que toma la aleatorización en realidad no es suficiente, ya que algunas dificultades no pueden ser superadas por la aleatorización.Pero hay algunos modelos de relajación de su problema.

Algunos de esos, y algunos detalles a mi respuesta se pueden encontrar en el artículo de Susanne Albers, Arindam Khan y Leon Ladewig denominados "algoritmos en línea mejorados para Knapsack y Gap en el modo de orden aleatorio" (consulte la Sección 1.1).