los problemas de acumulación

Question

Quiero escribir una pequeña utilidad de ayuda para organizar mi colección de libros de audio digitalizado.

Tengo un conjunto de carpetas que necesito para grabar en CD. Las carpetas no se pueden dividir:. Cada carpeta va en un disco

Quiero llenar los discos de la máxima eficiencia:

1. Minimizar el número de discos, y
2. El número de discos igualdad de condiciones, a maximizar el almacenamiento disponible del disco menos lleno (espacio restante 80 + 20 es mejor que 50 + 50).

¿Qué algoritmo se debe usar?

Answer 1

Esto se llama el Bin Embalaje Problema y es NP-duro, por lo que no es una algoritmo sencillo para resolverlo.

La solución que encontré funcionó mejor (me corrió un concurso de programación con una pregunta casi idéntica a ésta), fue ordenar las carpetas por tamaño y poner la carpeta más alto que todavía le queda en el disco hasta que esté lleno o todas las carpetas restantes son demasiado grandes para caber en el espacio restante.

Esto resuelve el problema rápidamente ya que después de la clase que el resto del algoritmo es O (n).

En la RAN I concurso, esto se tradujo en 74 discos en vez de los 79 que una solución ingenua alcanzaría para nuestra mayor conjunto de datos de prueba.

Answer 2

Si desea empaquetar los archivos / carpetas en un CD-R disco, lo que podría hacer esto de manera óptima en el tiempo de pseudo-polinomio. Para ello, usted tiene que ronda los tamaños de los archivos / carpetas en sectores, y cuente sectores disponibles en CD-R.

Después de esto, obtenemos discreta 1-D mochila problemas de acumulación del , que puede ser resuelto muy bien el uso de programación dinámica, con la complejidad O (n) ,

Para ser más específicos:

• O (n) = O (NO) , porque W es constante en su caso - W es la cantidad de sectores en CD- R.
• n cantidad de archivos / carpetas.

Para un mejor rendimiento puede cambiar el tamaño siempre sobre-aproximada de sectores, ejemplo de configuración:

• aproximado exceso de tamaño del sector 70k
• lo que hace 700M / 70k = 10k de todos los sectores en CD-R
• que debe calcular en segundos cuando los archivos cantidad menor que (1G / 10k = 100k) 100k - n <100.000
• en minutos cuando n <10'000'000

Lo que es más:

• solución puede ser muy bien en paralelo.

Tal vez la aplicación de este algoritmo en forma codiciosa "empacar un cd, el paquete siguiente CD" lo hará de trabajo?