Utilitaire pour distribuer de manière optimale des fichiers sur plusieurs DVD?

J'ai un tas de fichiers multimédias que je veux enregistrer sur DVD, mais comme chaque DVD ne contient que 4,5 Go, je dois trouver la façon optimale d'organiser les fichiers pour utiliser le nombre minimum de DVD (sinon l'espace vide laissé dans chaque Le DVD peut facilement s'additionner). Existe-t-il des outils pour vous aider?

Il y a de nombreuses années, il y avait un utilitaire DOS pour le faire avec des disquettes.

Essayez le DVD Span gratuit :

DVD Span est un outil de sauvegarde pour écrire le contenu de grands dossiers sur plusieurs DVD. DVD Span peut déterminer automatiquement la meilleure organisation de chaque disque afin d'ajuster la quantité maximale de données sur le nombre minimum de disques. DVDSpan est un excellent outil pour sauvegarder votre collection de musique, vos photos ou même l'intégralité de votre disque dur sur DVD. Et comme il produit des DVD (ou CD) normaux, aucun logiciel spécial n'est requis pour lire ou restaurer vos sauvegardes.

Ah, le problème du sac à dos . Je n'ai pu trouver qu'un seul solveur en ligne pour cela, ici . La taille de votre sac à dos serait de 4,5 Go et chaque paquet correspondrait à la taille de vos fichiers. Vous devrez masser un peu sa sortie pour l'adapter à votre application particulière, mais cela devrait être réalisable. Cela ne fonctionnera cependant pas très rapidement, car ce problème est difficile .

Aperçu

La réponse de Jeff Shattock est correcte: c'est équivalent (ou isomorphe, comme l'écrivent les mathématiciens) à un problème d'optimisation combinatoire, mais c'est équivalent au problème d'emballage bin à 1 dimension , pas au problème du sac à dos .

Heureusement pour vous, j'ai du code à partager qui résoudra ce problème pour vous ou toute autre personne ayant accès à un ordinateur Windows avec au moins la version 3.5 du .NET Framework installé.

Une solution approximative

1. Tout d'abord, téléchargez et installez LINQPad .

2. Deuxièmement, téléchargez la requête LINQPad que je viens d'écrire - voici le linq (ha) dans le fichier brut. Enregistrez-le en tant que fichier .linq et ouvrez-le dans LINQPad.

3. Modifiez les paramètres:

   Voici la partie du code de requête LINQPad que vous devez modifier:

   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";

   Changez binSizeMbla taille de votre «bac», par exemple CD, DVD, ex. int binSizeMb = 650;pour un CD.

   Remarque - la binSizeMbvaleur est interprétée comme ce qu'on appelle parfois un mégaoctet . Contrairement à mon enfance, lorsque tous les multiples d'octets étaient «binaires», parfois «MB» fait maintenant référence à un «mégaoctet décimal» ou exactement 1 000 000 octets, par opposition aux 1 048 576 octets d'un méga-octet (MiB), qui est utilisé dans mon code . Si vous souhaitez changer cela, changez la ligne const int bytesPerMb = 1048576;du code en const int bytesPerMb = 1000000;.

   Passez rootFileFolderPathau chemin complet du dossier contenant les fichiers que vous souhaitez «empaqueter dans des bacs», ex. string rootFileFolderPath = @"C:\MySecretBinFilesFolder";.

4. Exécutez la requête en appuyant F5sur ou en cliquant sur le bouton Exécuter en haut à gauche de l'onglet de requête.

Résultats

Le code de requête énumérera tous les fichiers du rootFileFolderPathdossier, récursivement, ce qui signifie qu'il inclura également des fichiers dans tous les sous-dossiers.

Ensuite, il créera des «bacs» pour les fichiers de telle sorte que la taille totale de tous les fichiers de chaque bac soit inférieure ou égale à la taille de bac spécifiée.

Dans le volet de résultats LINQPad, vous verrez deux listes.

La première liste contient tous les fichiers trouvés, classés par ordre décroissant de taille.

La deuxième liste est constituée des bacs créés en «emballant les fichiers», avec une liste des fichiers et leurs tailles, ainsi que la taille restante du bac.

Voici une capture d'écran montrant la deuxième liste et les deux premiers bacs créés:

Analyse du cursus

Selon Wikipedia, l'algorithme que j'ai utilisé - la stratégie First Fit Decreasing (FFD) - ne devrait pas être trop mauvais; Wikipédia déclare:

En 2007, il a été prouvé que le 11/9 OPT + 6/9 lié pour FFD est serré.

«OPT» fait référence à la stratégie optimale (comme quelque chose de potentiellement inaccessible, pas de stratégie réelle particulière).

Sur la base de mes souvenirs quelque peu flous des termes mathématiques impliqués, cela devrait signifier que la stratégie FFD devrait, au pire, emballer les éléments dans environ 1,22 fois le nombre de bacs qu'une stratégie optimale ferait. Ainsi, cette stratégie peut regrouper les éléments dans 5 cases au lieu de 4. Je soupçonne que ses performances sont susceptibles d'être très proches de l'optimalité, sauf pour des tailles spécifiques d'éléments «pathologiques».

Le même article Wikipédia déclare également qu'il existe un "algorithme exact" . Je peux aussi décider de mettre cela en œuvre. Je devrai d'abord lire l'article qui décrit l'algorithme.

Vous pouvez utiliser n'importe quel outil de compression qui permet de fractionner une archive je pense

Vous pouvez prendre l'une des variantes du programme dans le guide de l'auto-stoppeur de Haskell , peut-être après avoir travaillé sur une partie de ce didacticiel; le didacticiel est écrit pour résoudre exactement votre problème de distribution de choses sur plusieurs disques, grâce auquel la solution est affinée de manière incrémentielle, comme illustré par le passage suivant du chapitre 3 du didacticiel:

Assez de préliminaires déjà. allons emballer quelques CD.

Comme vous l'avez peut-être déjà reconnu, notre problème est classique. C'est ce qu'on appelle un "problème de sac à dos" ( google it , si vous ne savez pas déjà ce que c'est. Il y a plus de 100000 liens).

commençons par la solution gourmande ...

Plus d'idées: une question connexe

Voici une question similaire (mais pas la même: on ne lui demande pas d'optimisation), où vous pouvez trouver des solutions / programmes plus utiles pour votre tâche (s'ils seront affichés):

• /unix//q/10158/4319 - "Fractionner une grande arborescence de répertoires en morceaux de taille spécifiée?"

Quelques conseils pour comprendre la programmation dans le tutoriel suggéré

En général, le code Haskell est assez expressif (car Haskell est un langage de programmation à un niveau d'abstraction élevé), et peut donc être facilement saisi.

Lorsque vous regardez le code de l'une des solutions, n'oubliez pas que la structure de niveau supérieur du programme que nous voulons écrire est assez simple, comme indiqué dans le chapitre 1 du didacticiel:

Réfléchissons maintenant un instant au fonctionnement de notre programme et exprimons-le en pseudocode:

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

Semble raisonnable? J'ai pensé ainsi.

Simplifions un peu notre vie et supposons pour l'instant que nous allons calculer la taille des répertoires quelque part en dehors de notre programme (par exemple, avec " du -sb *") et lire ces informations depuis stdin.

et regarder de plus près les parties de la solution.

Il y a un certain temps, j'ai écrit un script PHP pour effectuer une telle tâche: https://bitbucket.org/borszczuk/php-backup-maker/

Essayez également Discfit, qui sélectionne les fichiers et les répertoires à copier sur différents disques:

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