¿Utilidad para distribuir archivos de manera óptima en múltiples DVD?

Tengo un montón de archivos multimedia que quiero grabar en DVD, pero como cada DVD solo tiene capacidad para 4,5 GB, tengo que encontrar la manera óptima de organizar los archivos para usar la cantidad mínima de DVD (de lo contrario, el espacio vacío que queda en cada uno DVD puede sumar fácilmente). ¿Hay alguna herramienta para ayudar con esto?

Hace muchos años había una utilidad de DOS para hacer esto con disquetes.

Prueba el DVD Span gratis :

DVD Span es una herramienta de respaldo para escribir el contenido de carpetas grandes en múltiples DVD. DVD Span puede determinar automáticamente la mejor organización de cada disco para ajustar la cantidad máxima de datos en la cantidad mínima de discos. DVDSpan es una gran herramienta para realizar copias de seguridad de su colección de música, fotos o incluso todo su disco duro en DVD. Y debido a que produce DVD (o CD) regulares, no se requiere ningún software especial para leer o restaurar sus copias de seguridad.

Ah, el problema de la mochila . Solo pude encontrar un solucionador en línea para esto, aquí . El tamaño de su mochila sería 4.5GB, y cada paquete sería el tamaño de su archivo. Necesitará masajear un poco su salida para adaptarse a su aplicación particular, pero debería ser viable. Sin embargo, esto no se ejecutará muy rápido, porque este problema es difícil .

Visión de conjunto

La respuesta de Jeff Shattock es correcta: esto es equivalente (o isomorfo, como escriben los matemáticos) a un problema de optimización combinatoria, pero es equivalente al problema de empaquetamiento del contenedor unidimensional , no el problema de la mochila .

Por suerte para ti, tengo un código para compartir que resolverá este problema para ti, o para cualquier otra persona, con acceso a una computadora Windows con al menos la versión 3.5 de .NET Framework instalada.

Una solución aproximada

1. Primero, descargue e instale LINQPad .

2. En segundo lugar, descargue la consulta LINQPad que acabo de escribir : aquí está el linq (ha) en el archivo sin formato. Guárdelo como un archivo .linq y ábralo en LINQPad.

3. Cambiar los parámetros:

   Aquí está la parte en el código de consulta LINQPad que debe cambiar:

   int binSizeMb = 4476; // This is the (floor of the) total size of a DVD+R reported by CDBurnerXP. string rootFileFolderPath = @"F:\2006 - Polyester Pimpstrap Intergalactic Extravaganza multicam";

   Cambie binSizeMbal tamaño de su 'contenedor', por ejemplo, CD, DVD, ej. int binSizeMb = 650;para un CD

   Nota : el binSizeMbvalor se interpreta como lo que a veces se denomina mebibyte . Al contrario de mi infancia, cuando todos los múltiplos de bytes eran 'binarios', a veces 'MB' ahora se refiere a un 'megabyte decimal' o exactamente 1,000,000 bytes, en oposición a los 1,048,576 bytes de un mebibyte (MiB), que se usa en mi código . Si desea cambiar esto, cambie la línea const int bytesPerMb = 1048576;en el código a const int bytesPerMb = 1000000;.

   Cambie rootFileFolderPatha la ruta completa de la carpeta que contiene los archivos que desea 'empacar en contenedores', ej. string rootFileFolderPath = @"C:\MySecretBinFilesFolder";.

4. Ejecute la consulta F5presionando o haciendo clic en el botón Ejecutar en la parte superior izquierda de la pestaña de consulta.

Resultados

El código de consulta enumerará todos los archivos de la rootFileFolderPathcarpeta, de forma recursiva, lo que significa que también incluirá archivos en todas las subcarpetas.

Luego, creará 'contenedores' para los archivos de modo que el tamaño total de todos los archivos en cada contenedor sea menor o igual que el tamaño especificado.

En el panel de resultados de LINQPad verá dos listas.

La primera lista es de todos los archivos que encontró, enumerados en orden decreciente por tamaño.

La segunda lista son los contenedores creados al 'empaquetar los archivos', con una lista de los archivos y sus tamaños, así como el tamaño restante del contenedor.

Aquí hay una captura de pantalla que muestra la segunda lista y los dos primeros contenedores creados:

Análisis de cursores

Según Wikipedia, el algoritmo que utilicé, la estrategia de primer ajuste decreciente (FFD), no debería ser tan malo; Wikipedia dice:

En 2007, se comprobó que el límite 11/9 OPT + 6/9 para FFD es ajustado.

'OPT' se refiere a la estrategia óptima (como algo potencialmente inalcanzable, no una estrategia real en particular).

Basado en mis recuerdos algo borrosos de los términos matemáticos involucrados, esto debería significar que la estrategia FFD debería, en el peor de los casos, empacar elementos en ~ 1.22 veces el número de contenedores que una estrategia óptima. Por lo tanto, esta estrategia podría agrupar elementos en 5 contenedores en lugar de 4. Sospecho que es probable que su rendimiento sea muy cercano al óptimo, excepto para tamaños de elementos 'patológicos' específicos.

El mismo artículo de Wikipedia también establece que existe un "algoritmo exacto" . Puedo decidir implementar eso también. Tendré que leer primero el documento que describe el algoritmo.

Podría usar cualquier herramienta de compresión que permita dividir un archivo, creo

Puede tomar una de las variantes del programa en la guía del autoestopista de Haskell , tal vez después de trabajar en alguna parte de ese tutorial; El tutorial está escrito en torno a resolver exactamente su problema de distribuir cosas en varios discos mediante los cuales la solución se refina gradualmente, como se ejemplifica en el siguiente pasaje del Capítulo 3 del tutorial:

Ya hay suficientes preliminares. vamos a empacar algunos CD.

Como ya habrás reconocido, nuestro problema es clásico. Se llama un "problema de mochila" ( búscalo en Google , si aún no sabes qué es. Hay más de 100000 enlaces).

empecemos por la solución codiciosa ...

Más ideas: una pregunta relacionada

Aquí hay una pregunta similar (aunque no es la misma: no se está pidiendo optimización allí), donde puede encontrar soluciones / programas más útiles para su tarea (si se publicarán):

• /unix//q/10158/4319 - "¿Dividiendo un gran árbol de directorios en fragmentos de tamaño especificado?"

Algunos consejos para comprender la programación en el tutorial sugerido

En general, el código de Haskell es bastante expresivo (ya que Haskell es un lenguaje para programar en un alto nivel de abstracción) y, por lo tanto, se puede comprender fácilmente.

Al mirar el código de una de las soluciones, recuerde que la estructura de nivel superior del programa que queremos escribir es bastante simple, como se indica en el Capítulo 1 del tutorial:

Ahora pensemos por un momento acerca de cómo funcionará nuestro programa y expresémoslo en pseudocódigo:

main = Read list of directories and their sizes.
       Decide how to fit them on CD-Rs.
       Print solution.

¿Suena razonable? Ya me lo imaginaba.

Simplifiquemos un poco nuestra vida y supongamos por ahora que calcularemos los tamaños de directorio en algún lugar fuera de nuestro programa (por ejemplo, con " du -sb *") y leeremos esta información de stdin.

y mire más de cerca las partes de la solución.

Hace años escribí un script PHP para hacer esa tarea: https://bitbucket.org/borszczuk/php-backup-maker/

Además, pruebe Discfit, que selecciona archivos y directorios para copiar en varios discos:

https://sourceforge.net/projects/discfit/