C#: Codifique para colocar MUCHOS archivos en un DVD de la manera más eficiente posible

Question

Necesito escribir una aplicación que tomará una lista de archivos (algunos grandes, otros pequeños) y los colocará en DVD (o CD, o lo que sea) lo más eficientemente posible. El objetivo de esta aplicación es utilizar la mayor cantidad del primer disco antes de pasar al segundo disco, llenar el segundo disco lo más posible antes de pasar al 3er disco, etc.

(Nota: La aplicación no tiene que grabar el DVD, solo tiene que encontrar el mejor ajuste posible).

Inicialmente pensé que tenía un buen plan de juego al generar una permutación de los archivos y luego revisar cada combinación para ver qué encajaba mejor. (Mi pedido de ayuda sobre esto se puede encontrar HERE)

Pero cuantos más archivos hay, más tiempo toma ... exponencialmente. Así que quería algunas de sus opiniones sobre cómo lograr esto de la mejor manera.

¿Alguna idea? Y, como siempre, siempre se agradece el código C#.

Answer 1

algoritmo simple:

1. ordenar la lista de archivos por tamaño del archivo
2. Encuentre el archivo más grande menor que el espacio libre que queda en el DVD, y agregarlo al DVD.
3. Si el espacio libre restante en DVD es más pequeño que cualquier otro archivo restante, inicie un nuevo DVD.
4. Repetir desde 2.

Answer 2

Lo que estás enfrentando está relacionado con el knapsack problem. La página enlazada de wikipedia contiene mucha más información, incluidas formas sugeridas de resolverla.

Answer 3

for each file 
is there enough room this dvd? 
    yes, store it here 
    no, is there room on another already allocated dvd? 
    yes, store it there 
    no, allocate another dvd and store it there 

Answer 4

Mientras que eso es un problema para resolver fresca en un programa para ciertas aplicaciones ... sin embargo, en su aplicación, por qué no usar WinRAR o cualquier otro programa de archivo que tiene la capacidad de dividir el archivo en trozos de archivos de tamaño específico. Podrías hacer cada pedazo del tamaño de un DVD y luego simplemente grabarlo.

EDITAR: un problema con el que se encontraría es que si uno de sus archivos es mayor que el tamaño de su medio, no podrá grabar ese archivo.

Answer 5

¿Qué tal si comenzaste colocando tantos de los archivos más grandes que puedas en un DVD y luego llenándolos con tantos archivos pequeños como puedas (empezando por el más pequeño).

Repita este proceso con los archivos restantes para cada disco.

No estoy seguro de que le proporcione una cobertura/distribución perfecta, pero creo que podría ayudarlo a resolver sus necesidades.

Answer 6

utilización dar marcha atrás para obtener el conjunto óptimo de archivos para grabar a DVD 1, a continuación, excluirlos de la lista y dar marcha atrás en los archivos restantes para obtener el llenado óptimo para dvd 2 y así sucesivamente

Answer 7

Para alguien todavía interesado en esta pregunta ... Escribí una utilidad que utilicé para un propósito similar de ajustar archivos en un conjunto de discos/discos. Utiliza una interfaz de línea de comandos/basada en archivos. Las versiones están disponibles en C, C++, & Java (no C#).

http://whizman.com/code/diskfit.tgz

información más detallada se encuentra en el diskfit.tgz: Doc archivo/diskfit.txt.

(AGPL3)

Podríamos caracterizar la pregunta 0-1 múltiple mochila, o envasado bin lineal. (. Gracias Jon-skeet para el enlace sobre el problema de la mochila)

Dthorpe resuelve embalaje bin lineal, por exactamente suficientes papeleras/discos para adaptarse todos los archivos [muy bien O (n) u O (n lg n) rápida - también puede ser factible en una hoja de cálculo sin tener que escribir una secuencia de comandos].

Básicamente, diskfit (anteriormente ligado utilidad) Salidas de calificación grupos de archivos en torno a 0-1 sola mochila, y el usuario elige un disco grupos de archivos para montar en el disco-set - ayudar a la usuario (pero no se automatiza por completo) hacia ambos:

• empaque de contenedor lineal - para el conjunto completo de discos;
• 0-1 mochila múltiple: para cada subconjunto de discos 1..k del conjunto de discos completo (donde los archivos son prioritarios, también difieren en el valor).

Opción programática completa del conjunto de discos completo, sería una característica adicional. No sería suficiente aplicar una solución de una sola mochila 0-1, automáticamente por disco [ávidamente]. (Considere 3 mochilas de capacidad 6 y los artículos disponibles con el mismo valor y los pesos de: {1, 1, 2, 2, 3, 4, 5}. Aplicando 0-1 mochila a la primera mochila de forma aislada elegiría {1, 1, 2, 2} para obtener el valor total 4 - después de lo cual no podemos incluir todos los restantes 3 artículos en el restante & terceros mochilas - mientras que sabemos que podemos caber todos los artículos en las 3 mochilas como {1, 2, 3} & {1, 5} & {2, 4}.)

Answer 8

he encontrado una gran cantidad de herramientas que se supone que para resolver este problema, pero todos tratan de minimizar el TOTALES número de disco utilizado, mientras que yo estaba solo intereste d en el subconjunto ÚNICO de archivos que mejor se ajusta a un disco SIMPLE.

Así que he terminado de escribir mi propia herramienta llamada "ss" (del algoritmo "subconjunto suma" que se basa en). La herramienta todavía tiene errores y no puede volver a generar directorios, pero me funciona. :)

Answer 9

Este problema es Bin Packing Problem y es NP completo, lo que significa que si quieres una solución verdaderamente óptima necesitarás tiempo exponencial. Sin embargo, hay métodos que ofrecen soluciones menos que óptimas pero que se ejecutan mucho más rápido.

Supongamos que tenemos una lista ilimitada de discos. Tome cada archivo ordenado en tamaño descendente, luego agregue cada archivo al primer disco que encaje. Esto se denomina Disminución del primer ajuste y toma 11/9 discos OPT + 6/9 en el peor de los casos. Si elige archivos en orden aleatorio, en su lugar necesita 11/9 OPT + 1 discos.

Hay algoritmos que encapsularán las cosas, consulte el enlace de wikipedia anterior para obtener más detalles.