[l-desarrollo] Algoritmos de programación dinámica para una variación del Knapsack Problem

[Daniel Peraza]

Saludos amigos. Por cosas de la vida me he topado con un cliente, que maneja operaciones logísticas de transporte de mercancías. Este cliente debe despachar los artículos detallados en una serie de facturas, pero respetando la capacidad máxima del transporte y también el valor total de los artículos a transportar. Por ejemplo, un transporte puede cargar 5 toneladas de mercancías, por un máximo de 10 millones de BsF. Si se exceden estos límites, una factura puede ser dividida en varias notas de entrega. El problema consiste en distribuir los ítems de manera de transportar la máxima cantidad posible de los mismos, respetando los límites establecidos por las políticas de la empresa y capacidad de los transportes.

Desde mi punto de vista, esto ante una variación del Bounded Knapsack Problem, sólo que con la restricción adicional del valor de las mercancías. Es como decir que el ladrón que entra a la tienda, sólo puede robarse cierta cantidad de artículos sin ser descubierto, además de que no puede llevar exceso de peso.

Me gustaría conocer la opinión de ustedes, y también algún link que puedan aportar con algún algoritmo greedy o dinámico.

[Werner Echezuria]

El día 20 de noviembre de 2012 00:54, Daniel Peraza
<daniel...@gmail.com> escribió:

> _______________________________________________
> l-desarrollo mailing list
> l-desa...@velug.org.ve
> http://listas.velug.org.ve/mailman/listinfo/l-desarrollo
>

La página Rossetta Code contiene implementaciones de una gran cantidad
de algoritmos en varios lenguajes, aqui tienes por ejemplo el del
Knapsack problem:
http://rosettacode.org/wiki/Knapsack_problem/Bounded
_______________________________________________
l-desarrollo mailing list
l-desa...@velug.org.ve
http://listas.velug.org.ve/mailman/listinfo/l-desarrollo

[Ernesto Hernández-Novich]

On Tue, 2012-11-20 at 00:54 -0430, Daniel Peraza wrote:
[...]

> Desde mi punto de vista, esto ante una variación del Bounded Knapsack
> Problem, sólo que con la restricción adicional del valor de las
> mercancías.

Sería el Knapsack Problem si tuvieras *un* sólo camión, pero aún si
pudieras restringirlo a llenar de a un camión a la vez, tienes al menos
dos restricciones de empaquetado (peso *y* valor) y seguramente también
tendrás la restricción de volumen o dimensiones de la carga, así que es
una instancia del 0-1 m-Dimensional Knapsack Problem (MKP) — ese
problema es NP-Hard (*creo* que es NP-Completo, pero eso es un detalle
anecdótico) de modo que programación dinámica no aplica porque tendrá
complejidad exponencial.

Eso quiere decir que el algoritmo típico que vas a encontrar en
cualquier libro de algoritmos (Cormen, Sedgewick, etc.) para resolver
Knapsack te sirve de poco y nada. En todo caso, Perl provee
Algorithm::Knapsack listo para usar y en Haskell hay soluciones
polimórficas dinámicas y no dinámicas que no pasan de 20 líneas que
puedes encontrar con simples búsquedas en Google. Encontré [1] entre mis
bookmarks, que puede ayudarte o impulsarte a saltar de un puente.

Para tu problema pareciera ser más apropiado utilizar un algoritmo
genético convencional, o uno probabilístico de la familia ACO (Ant
Colony Optimization).

[1] http://www.diku.dk/users/pisinger/95-1.pdf
--
Ernesto Hernández-Novich - @iamemhn - Unix: Live free or die!
Geek by nature, Linux by choice, Debian of course.
If you can't aptitude it, it isn't useful or doesn't exist.
GPG Key Fingerprint = 438C 49A2 A8C7 E7D7 1500 C507 96D6 A3D6 2F4C 85E3

[Daniel Peraza]

Gracias Sr. Novich, esa la orientacion que buscaba para mejorar mis esfuerzos. Ahora se que debo consultar mas el area de IA.