Foro de elhacker.net

Buenas, considerando el problema de la mochila binaria, habría alguna manera de resolver el problema rapidamente teniendo en cuenta que la capacidad de la mochila puede ser increiblemente elevada? si fuera que haya una solución solamente para este problema serviría para algo practico? Muchas gracias.

Puede verse desde muchos puntos de vista y posibles soluciones, que tal si planteas algún escenario real sobre algún proyecto que estés realizando? de esa manera podríamos ver si talves tu problema tiene una solución alternativa, por ejemplo utilizando alguna tecnología o librería que ya esté diseñada para el propósito que buscas, por ejemplo, si fuera una aplicación analítica utilizaría una base de datos desnormalizada o con indices de valores de tipo en memoria y luego hacer un ordenamiento para ir llenando la mochila, de esa manera le delego la carga y la tarea de optimización de acceso a los datos al motor de la base de datos ya que está diseñada para ello a bajo nivel para el ahorro de consumo de recursos de cpu y memoria.

En mi caso lo que haría simplemente es realizar un ordenamiento de todos los items por valor de prioridad (segundo valor), y luego ir a buscar el valor mayor que cabe dentro de la mochila y luego ir buscando hacia el siguiente de mayor valor de prioridad hasta que ya no quepan más, eso maximizaría el contenido. Esto podría realizarse con una sola consulta sql teniendo el valor máximo de la mochila.

Saludos.

La pregunta que tengo seria esa, que situación real se puede llevar al caso del problema de la mochila y de que manera se plantiaría como tal. Por ejemplo algún tema de ingeniería, economía o biología.

Aclaración: como problema de la mochila me refiero al problema original, donde hay elementos con pesos y "beneficios" en donde dado una capacidad, que no debe ser superada, se elija la combinación de mayor rédito posible.

Todo esto llega de que estoy haciendo una análisis para tener la solución optima al problema de la mochila de manera eficiente.

Se me ocurren algunas situaciones reales, por ejemplo en el área de la construcción, tienes varias opciones para realizar un mismo proyecto y tendrías que combinarlas para poder llegar a la mejor opción que se la de mayor calidad con el menor costo, y conseguir la mayor rentabilidad del proyecto, al momento de armar un equipo de computo tendrías que elegir la mejor combinación de componentes al mejor precio para lograr el máximo performance posible, son algunos ejemplos que se me vienen a la mente...

Saludos

Un carrito de compras para un sitio web, necesitas crear cajas de regalos a un precio determinado por el usuario donde cada ítem dentro de la caja puede tener un beneficio distinto según precio calidad, también se puede aplicar a un sistema de selección de envío de productos por avión, sólo te dan un tamaño y peso máximo y debes poder enviar lo mejor que puedas según una selección de productos.