problème d'emballage

Question

Je veux écrire un petit utilitaire d'aide pour organiser ma collection de livres sonores numérisés.

J'ai un ensemble de dossiers que je dois écrire sur des CD. Les dossiers ne peuvent pas être divisés. Chaque dossier passe sur un disque

Je veux remplir les disques le plus efficacement possible:

1. Réduire au minimum le nombre de disques et
2. Le nombre de disques étant égal, à optimiser le stockage disponible du disque moins rempli (80 + 20 espace restant est meilleure que 50 + 50).

Quel algorithme dois-je utiliser?

Answer 1

Ceci est appelé Bin Emballage problème et est NP-dur, donc il n'y a pas algorithme simple pour le résoudre.

La solution que j'ai trouvé fonctionne le mieux (j'ai couru un concours de programmation avec une question presque identique à ce sujet), était de commander les dossiers par la taille et de mettre le plus grand dossier qui reste unique sur le disque jusqu'à ce qu'il soit plein ou tous les dossiers restants sont trop volumineux pour tenir dans l'espace restant.

Cela résout le problème rapidement car après le tri le reste de l'algorithme est O (n).

Dans le concours je courais, cela a abouti à 74 disques au lieu de 79 qu'une solution naïve réaliserait pour notre plus grand ensemble de données de test.

Answer 2

Si vous souhaitez regrouper vos fichiers / dossiers sur un CD-R disque, que vous pouvez le faire de façon optimale dans le temps pseudo-polynomiale. Pour ce faire, vous devez tailles rondes de fichiers / dossiers dans les secteurs et les secteurs disponibles sur comptiez CD-R.

Après cela, nous obtenons discrète 1-D problème d'emballage havresac , qui peut être résolu en utilisant bien la programmation dynamique, avec la complexité O (n) ,

Pour être plus précis:

• O (n) = O (nW) , la cause W est constante dans votre cas - W est quantité de secteurs sur CD- R.
• n quantité de fichiers / dossiers.

Pour de meilleures performances, vous pouvez toujours la taille trop approximative des secteurs, exemple de configuration:

• Taille du secteur approximées 70k
• ce qui rend 700M / 70k = 10k de tous les secteurs sur CD-R
• qui doit calculer en quelques secondes lorsque les fichiers montant inférieur (1G / 10k = 100k) 100k - n <100'000
• en quelques minutes lorsque n <10'000'000

Quoi de plus:

• solution peut être bien en parallèle.

Peut-être l'application de cet algorithme de manière gourmande « emballer un cd, cd prochain pack » fera le travail de ce?