Para un montón de artículos con valores y pesos , y con un peso total que nuestra bolsa puede llevar, ¿cómo logramos el máximo valor total sin romper la bolsa? Dantzig propuso que consideráramos la relación , y agregue artículos para los que esta proporción sea mayor hasta que se llene la bolsa. Pero esto se considera como una solución aproximada.
También he estado pensando en este problema. Se me ocurrió la misma solución que Dantzig e incluso la probé para el problema. Por supuesto, sospeché de mi prueba incluso antes de saber que el método había sido propuesto antes (ya que implicaría que ). Ahora sospecho aún más.
Así que sácame de mi miseria. ¿Por qué no funciona?
No funciona porque no funciona.
di que tienes y hay tres clases de objetos:
Si miras , tipo gana, entonces tomas un tipo objeto y llene el espacio restante con un tipo , por valor total .
Pero la solución óptima requiere cinco tipos objetos por valor total .
Podríamos caracterizar la dificultad general de la siguiente manera: una elección que parecía buena al principio se topó con problemas más tarde, porque nuestra elección inicial de , óptimo a corto plazo, nos obliga a tomar lo muy malo después. La solución óptima toma muchas opciones que parecen subóptimas a corto plazo, pero que funcionan bien juntas.
Esto es bastante típico de los problemas NP-completos. Tienen muchas partes que interactúan de manera complicada, por lo que los efectos de una elección particular en una parte del problema no pueden localizarse, pero tienen implicaciones de gran alcance para las elecciones realizadas en otros lugares. Compare esto con el prototípico problema NP-completo, CNF-SAT, donde las partes son cláusulas lógicas que contienen varios componentes cada una, pero cada componente puede aparecer en múltiples cláusulas. Cada elección sobre el valor de un componente de una cláusula puede tener efectos de largo alcance en las otras cláusulas.
O de manera similar, considere el embalaje en contenedores. Los artículos que encajan de manera óptima en el primer contenedor pueden resultar justo lo que se necesita para llenar el espacio en los contenedores posteriores, de modo que un empaque óptimo del primer contenedor puede generar una ganancia a corto plazo a expensas del empaque general; una solución óptima general puede empacar el primer contenedor de manera subóptima para guardar ciertos artículos especiales para más adelante.
Para que quede claro: si llena artículos de acuerdo con su relación valor/peso hasta que no pueda caber más artículos en este pedido, el resultado es óptimo , si el peso acumulado para entonces coincide exactamente con el espacio disponible. En otras palabras, SIEMPRE es óptimo para el peso total que acumuló. Supongo que este es el resultado que tenías en mente. No es difícil de probar y se puede encontrar en cualquier introducción a los problemas de la mochila, por ejemplo en "Martello, S. & Toth, P. Problemas de la mochila: algoritmos e implementaciones informáticas. John Wiley & Sons, 1990"
Sin embargo, como se discutió en la primera respuesta y los comentarios allí, su método obviamente no siempre es óptimo si termina sin llenar la bolsa por completo. Pensar en para grande y artículos (peso , valor ) (peso , valor ). Entonces tu algoritmo termina con y un valor de , cuando en cambio podría haber tenido con un valor de . Sin embargo, es trivialmente óptimo para el peso que alcanza, es decir, óptimo para una mochila con peso total .
naslundx
tonyk