Au fait, au sujet du pb d'optimisation d'un programme de gravure de CD
Au fait, au sujet du pb d'optimisation d'un programme de gravure de CD - Algo - Programmation
Sujets relatifs:
- [PHP] questions au sujet des saut de lignes, puis des quote
- [VC++] Structure d'un programme
- comment creer un "programme" qui envoit des netsend en boucle ? .BAT?
- programme pour faire du php, mysql
- [Optimisation Mysql] Qui peut m'aider ?
- [Débutant prog] Un programme pour gérer une auto-école..quel language?
- [C] petit programme tout con ... pour ceux qui connaissent ?
- [sujet clos] [ C ] Comment visualiser les fonctions exporté d'une Lib
- un site web est-il un programme ?
- comment faire pour k1 programme clic de lui-meme
Marsh Posté le 13-06-2002 à 05:35:48
Il y a pas mal de temps, un long topic de ce forum avait concerné la realisation d'un programme minimisant le N nombre de CDs servant a graver un ensemble de fichiers {f} de taille variable (mais inferieurs a la taille max gravable).
Certaines heuristiques avaient ete proposées, mais pas de programme optimal.
Je sais maintenant pourquoi: dans le cas general, c'est un problème NP-difficile.
(dans le cas ou chaque fichier a une taille minimale strictement superieure a 1/3 de la taille d'ubn CD, cela devient un pb polynomial).
[reference: C. Prins, algorithmes de graphes, p.232]
A+,
A+,
---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --