¿Cómo distribuye Python cadenas de diferentes longitudes en N archivos de la manera más uniforme posible? La cadena de cada línea se toma como un todo y no se puede dividir.
Una variante del problema de la mochila. En otras palabras, es un algoritmo de agrupación unidimensional.
Imagina cada línea de cuerda como un elemento, y la longitud de la cuerda es el tamaño del elemento. Cada archivo equivale a una caja diferente. El tamaño de la caja es fijo, y la suma de los volúmenes de los artículos cargados no puede exceder la capacidad total de la caja.
La pregunta es: cómo utilizar la menor cantidad de cajas posible para cargar todos los artículos, o: cómo hacer que tantas cajas como sea posible sean más eficientes en cuanto a espacio, y cuestiones similares relacionadas.
La respuesta a este tipo de preguntas no es un simple número, requiere una estrategia: los artículos 1...n se empaquetan en cajas 1...m (mlt; =n).
Para bidimensional o tridimensional, la diferencia radica principalmente en la complejidad de la solución, pero en términos generales, la idea de una solución se puede extender de una dimensión a dos o tres dimensiones.
Actualmente no existe una solución óptima global para este tipo de problemas (es decir, ningún algoritmo puede asegurar los mejores resultados en todas las situaciones), pero sí se pueden obtener soluciones óptimas locales. Existen muchos algoritmos, como el algoritmo codicioso más común o la programación dinámica.
La idea del algoritmo codicioso es relativamente simple: ordena todos los elementos de mayor a menor, toma una caja e intenta cargar el elemento más grande. Si no se puede cargar, intenta hacerlo. cargue elementos más pequeños, y así sucesivamente hasta que todos los elementos estén cargados en todas las cajas.
El algoritmo es muy sencillo, pero muchas veces los resultados obtenidos no son los ideales.
Algoritmo codicioso
La idea de la programación dinámica es que cada vez que se carga un artículo en la caja, surge un nuevo problema: en función de todos los artículos descargados y el espacio restante de la caja Como condición, ¿cómo instalarlo? Habrá muchos problemas de este tipo dependiendo de los elementos cargados. Elegir el método con el menor espacio restante es la solución óptima local. En términos generales, esto es más adecuado para manejarlo mediante recursividad, pero su complejidad es mucho mayor que la del algoritmo codicioso.
Programación dinámica
Por supuesto, existen otros algoritmos. Diferentes algoritmos tienen diferentes ideas, complejidad y alcance de aplicación. Por lo tanto, no hay necesidad de insistir en lo mejor, sólo ser lo mejor posible.
De lo contrario, se podrían publicar muchas tesis doctorales sobre el problema del boxeo.
En respuesta al problema del tema, la solución del algoritmo codicioso es leer cada línea, luego ordenarla y cargar el cuadro con el mayor espacio restante de mayor a menor (es decir, cargar la caja con menor contenido).
Puede consultar los siguientes métodos de procesamiento: