¿Cómo crear una función de embalaje optimizada en python?

Question

Me han dado la tarea de crear un módulo de envío para un sistema de tienda en línea. Puede ser un poco exagerado, pero me gustaría crear uno que sepa cómo empacar paquetes de la manera más optimizada. Habiendo aprendido la programación simplemente al hacerlo, esta es un área en la que aún no tengo conocimiento. De todos modos, puedo dar una breve descripción del problema real.

Por lo tanto, cuando los usuarios por cosas en tiendas virtuales tendrán x productos en su carrito con tamaños y peso posiblemente diferentes. Así que quiero dar esa lista de productos a la función y dejar que descubra cómo estos productos deben empaquetarse en paquete (s).

• longitud máxima de parcela: anchura 100
• max de la parcela: altura 50
• max de la parcela: peso 50
• max de la parcela: 20

Cada producto tiene un peso , largo, ancho y alto también.

Dado que los paquetes y productos son básicamente cajas, supongo que esto sería bastante complejo, ya que hay diferentes formas de colocar los productos dentro del paquete. Mi objetivo no es hacer la función de embalaje perfecta, pero me gustaría hacer algo mejor que simplemente poner productos dentro del paquete hasta que se alcance un límite.

Ahora, no espero que ustedes hagan esto por mí, pero lo que me gustaría preguntar es tres cosas.

1. ¿Dónde puedo encontrar buenos recursos en línea que me enseñarán los conceptos básicos necesarios?
2. ¿Hay algunas herramientas nativas de python que sería bueno usar?
3. Algunos indicadores de lo que tengo que tener en cuenta, trampas, etc.

Como dije, no pienso que esto sea perfecto y el 100% optimizado, pero me gustaría terminar con algo eso se acercará No me gustaría que los usuarios sientan que la tarifa de envío será mucho más alta de lo que realmente es.

Answer 1

El hecho de que tenga altura, longitud y ancho lo hace más difícil que un simple problema de mochila. Aquí hay una discusión interesante de un 3D knapsack problem.

Aquí hay un paper on the topic del mismo tipo.

Answer 2

Esa es su típica knapsack problem. Se pueden encontrar muchas soluciones para diferentes idiomas en Rosetta Code.

Answer 3

Esto parece un buen problema para aplicar the simplex algorithm o algún tipo de genetic algorithm. Si nunca escuchó sobre este último, le recomiendo que lea sobre ellos. Como puedo ver en su pregunta, usted está haciendo esta mejora porque le gusta hacer que las cosas funcionen de manera óptima, y ​​no porque se lo hayan indicado. ¡Imagínese cuando les diga que aplicó una técnica de Inteligencia Artificial para resolver su problema!

Existen muchos algoritmos directos que resuelven su problema, pero esta puede ser una gran oportunidad para aprender algunos cálculos evolutivos. Algunos enlaces interesantes sobre algoritmos genéticos [todo el mundo, se siente libre de editar y añadir]:

1. These pages introduce some fundamentals of genetic algorithms.
2. Genetic Algorithms in Plain English

suerte con eso!
Manuel

Answer 4

Este una vieja pregunta, pero por si acaso alguien se tropieza esta biblioteca de Python ... hay llamada pyshipping que resuelve este problema:

https://pypi.python.org/pypi/pyShipping