Bonjour à tous!!
J'ai un petit problème d'algo...
Voila je voudrai faire un petit programme (certainement un script, mais je n'ai pas encore choisi de language) pour optimiser la place de mes fichier à graver.
En gros j'ai une liste de fichiers de différentes taille et je voudrai les graver sur des dvd de 4.5Go
Je voudrai que mon programme soit capable de me dire quoi graver sur chaque dvd pour utiliser le moin de DVD possibles.
J'ai environ 100 Go de données répartie en 49 fichiers insécables de 80 Mo à 4,2Go
 
Exemple:
Fic1 : 2.8Go
Fic2 : 3.4Go
Fic3 : 500 Mo  
Fic4 : 900 Mo
Fic5 : 1 Go
 
Je voudrai que le prog me dise :  
DVD1 : Fic1 + Fic3 + Fic4 = 4.3Go
DVD2 : Fic2 + Fic5 = 4.4Go
   
 
et pas bêtement:
DVD1 : Fic1 = 2.8Go
DVD2 : Fic2 = 3.4Go
DVD3 : Fic3 + Fic4 +Fic5 = 2.4Go
   
 
Et donc le pb c'est que je me retourne la cervelle la dessus sans trouver la moindre solution... Peu être du récursif, mais mon crane de débutant décroche trop vite...  
Vous pouvez m'aider?

algo : sac à dos

....  

Pauvre willynuisance, tu en fais une drôle de tête !
 
Pourtant, Taz a raison. C'est exactement le "knapsack problem" comme on dit chez nos voisins de la fière Albion. Avec le moteur de recherche de lunettes de protection (google), tu trouveras beaucoup de sites qui en parlent, par exemple pour la théorie, voir http://www.nist.gov/dads/HTML/knapsackProblem.html ; pour du code C, voir
http://www.darkridge.com/~jpr5/arc [...] de160.html ; pour du code Java, voir http://www.aridolan.com/ga/gaa/gaa.html ; et le meilleur pour la fin, pour du code en Lisp, voir http://www.cs.usu.edu/~vkulyukin/v [...] index.html
 
Bon courage !

google != goggle

Salut!
Merci olivthill, mais je ne connaissai pas du tout ce concept, et avec ce que Taz me disai.....  
Mais merci quand même a toi aussi taz, en cherchant après sur le forum, j'ai que Taz avait déja répondu à plusieur topic de ce genre  
Donc apparement je n'invente rien  
Encore merci à vous deux!!

Oui, je me suis trompé, et je suis content que la remarque m'ait été faite, parce que sinon j'aurais refait plusieurs fois la même erreur et me serait rendu ridicule à nouveau comme je le suis actuellement. Les lunettes de protections sont des goggles et non pas des googles.

Drapal sur ta remarque. Chaque fois que tu feras une intervention, on pourra mettre un lien pour rappeler comment, ce jour, tu t'es ridiculisé.
 

euuhh..... OK pr google,  
Sinon pour le code j'ai compris beacoup de chose, mais je pense pas être capable de coder un truc comme ça.....
quelqu'un aurait-il un code à proposé pour ça?

  Ce n'est pas charte-compliant. Et accessoirement, c'est stupide.
 
Si tu ne comprends pas la théorie, tu ne comprendras rien au code tout fait. Si c'est au-dessus de tes capacités, soit mets-toi à jour, soit fais qq chose à ta portée.
 
Inutile d'essayer de conduire une F1 si tu t'en sors pas avec une C2, n'est-ce pas.    

Je suis bien d'accord avec toi Sircam, et je ne compte pas m'arrêter la en dévloppement!    
Mais ceci ne remet pas en cause le fait que j'ai besoin de trouver un prog qui fait le travaille dont j'ai besoin...  
Donc je me disai, dans la foullé,   si quelqu'un savai ou trouver un code qui fait ça, ou quelquechose qui s'en approche et que je pourrai adapter ça me rendrai bien service pour éviter de gaspiller 2 ou 3 DVD(au prix qu'ils coutent )
Sinon vous n'êtes pas d'accord avec ça tant pis, je ne veux froisser personne, je me débrouillerai d'une manière ou d'une autre
Merci à vous

Tu n'as rien écouté de ce que j'ai dit.
 
HINT : Et si tu l'écrivais toi-même ?
 

Tu peux chercher aussi bien que nous.

Pour rester charte-friendly    
 
Si tu ne t'en sors pas avec cet algo, tu peux essayer quelque chose de moins efficace, mais plus simple à comprendre...
 
En réflechissant : comment tu ferais, toi, pour ranger le plus rationnellement possible tes fichiers ?
Moi, j'attaquerais comme ça :
Je trie mes fichiers du plus gros au moins gros.
Tant qu'il me reste un fichier,
   Je trie mes DVD du plus rempli au moins rempli.
   Pour chaque DVD
      J'essaye de caser mon fichier.
   Si je ne réussi pas à le caser dans un DVD entamé,
      Je le mets sur un DVD vierge.
 

Trié => Fic2, Fic1, Fic5, Fic4, Fic3.
Je mets Fic2 dans un DVD vierge (DVD1).
Fic1 ne passe pas dans DVD1 => Je le mets dan DVD2.
Fic5 passe dans DVD1 ( 3.4 + 1 = 4.4 < 4.5 )
Fic4 ne passe pas dans DVD1 => Il passe dans DVD2 ( 2.8 + 0.9 = 3.7 < 4.5 )
Fic3 ne passe pas dans DVD1 => Il passe dans DVD2 ( 2.8 + 0.9 + 0.5 = 4.3 < 4.5 )
 
Au niveau programmation, ça devrait rester simple...
 

macgawel> Tu n'aurais pas un morceau de code qui fait ce que tu dis, en passant ?

willynuisance, en Perl il y a ce module qui fait ce que tu cherche:
http://search.cpan.org/~mschilli/A [...] ketizer.pm

jviens de tester la solution de macgawel
ca marche nikel
c de loin la plus rapide (compare a knapsack, bloatware inside vu quil teste tout les possibles) , et la plus facile a faire (5 min 10 lignes)

Et puisqu'ici on aime la precision, c'est "goggles" et pas "goggle".

J'aimerais surtout voir la même précision dans l'utilisation du Français... Parce que pour une élite, c'est loin d'être fameux.    

Merci matafan et sircam pour ces remarques de bon aloi.
 
Par ailleurs, mon dictionnaire (Random House Webster's Unabridged Dictionary) ne comporte aucune entrée pour "google", mais il en a une pour "googol" qui signifie, je vous le donne en mille

Salut , je cherche depuis quelques temps un soft pour me faire ça ? tu peux m'aider peut etre ?    
 
Merci
 
PS : je ne suis pas developpeur donc si vous avez une piste d'un soft deja compilé (pour windows) MERCI  
 
J'ai trouvé ça -> http://www.abo.fi/~jmunsin/gcombust/
"Maximize disk by hinting which directories/files to use (binpacking/knapsack), reads cd size from disk "
 
mais je ne trouve pas son equivalent sous windows ...

j'ai fait un bout de prog qui donne ça comme resultat :
 

 
je termine l'interface graphique et tu l'aura dispo en telechargement dans la semaine.
 
pour voir le code source :
 
http://www.lbasic.fr/forum/viewtopic.php?p=6522#6522
 
@++

Ah c'est vraiment génial ça !
mais je m'étonne de ne pas avoir trouver de soft sur internet avec déja cette option intégré !
 
m'enfin
 
faudrait plus que ton soft soit capable de regarder tous les fichiers d'un meme dossier et de creer des dossiers de taille défini en glissant les fichiers directment et là ça serait super top !
 
EDIT : ou au moins est il possible de faire une macro Excel pour que j'ai juste à copier coller la liste de mes fichiers à la limite ?
 
 
j'ai 400 Go de video allant de 5Mo à 3Go à faire rentrer (dans n'importe quel ordre) sur le moins de dvd possible...  
 
 
 
Un grand Merci  

je te mets l'option souhaitée....
je reposterais quand ce sera fait.
 
@++

drapal

trevor -> drapal ???
 
 
Merci beaucoup lbasic  

oui je poste un message, pour garder trace de ce topic car il m'intéresse, je mets un drapeau (avec un jeu de mot à la con)

Cf Ignition que je développe : http://www.kcsoftwares.com/?ignition ....

En plus je peux piloter la gravure avec CopyToDVD depuis Ignition

 
que dire ? bah c'est exactement ce que je cherchais !!!!
 
trop fort ! un grand merci !    
 
manque juste une petite option pour deplacer les fichiers (optimisés) directement dans des dossiers de la taille désiré.
 
 

C'est marrant, j'avais fait un projet à l'école la-dessus : un peu de recherche avec un prof de biomimétique. La seule différence avec ton pb, c'était qu'on n'était pas obligé de prendre tous les fichiers donnés en entrée pour les mettre sur des CDs (ou autre support).
Voici un composant en delphi : http://www.2001-space-odyssey.net/ [...] cd_cmp.zip
et voici qq infos sur ce composante : http://www.2001-space-odyssey.net/~chris/opt_cd.html (désolé, mon site est vieux, tout pourri, j'ai pas eu le temps de le remettre à jour et bien développé).
 
Sinon, le topic qui avait précédé le développement de ce composant : http://forum.hardware.fr/hardwaref [...] 4853-1.htm

la méthode du sac à dos, c'est bien la même que celle utilisé par les FS afin de limiter la fragmentation, c'est ça ?
(à savoir, systématiquement chercher à se caser dans le plus grand trou disponible)

ps: ouais, nan, j'ai dis une connerie

le sac à dos est pas appelé aussi algo LPT, non?

possible à vérifier.
 
Seule info sure : c'est un problème NPC (NP Complet) pour lequel il n'existe pas de solution en temps polynomial.
 
Mais sur des domaines commes des fichiers sur CD voire DVD il y a des solutions (cf Ignition) qui convergent en temps correct.

Salut kyle,
 
Bravo pour ta belle réalisation. J'ai commencé ma version, donc je vais la finir. La mienne sera quand même plus minimaliste que ce que j'ai vu dans ta copie d'ecran.
 
Je suis en plein demenagement, donc c'est dur dur, et au 31 decembre, couik - plus de connexion donc je vais essayer de terminer avant.....
 
voici quelques images :
 

le tutoriel d'aide.
 

l'interface principale.
 

la liste des fichiers avant le tri
 
@++

Merci encore !
 
Tiens moi au jus lbasic pour que je puisse tester ton soft  

Si cela vous intéresse, freeware : http://lars.werner.no/wordpress/?page_id=2
 
Je sais que, surtout dans cette catégorie, le plaisir est de trouver une "méthode" pour y parvenir, mais pour les feignasses... et puis pour ceux qui codent, peut-être cela peut-il donner des idées quant aux améliorations à apporter.
 
Pas essayé.