optimisation du nombre de disques de gravure

[threepwood]

Bonjour à tous,

J'avoue que je sèche sur un petit problème que j'aimerais résoudre, je compte sur vos lumières pour m'aider:

J'ai une certaine quantité de fichiers de tailles très diverses à graver sur plusieurs DVD. Le but du jeu est de trouver un arrangement de fichiers sur chaque DVD pour en minimiser le nombre et ainsi réaliser une économie de supports.

L'exemple qui me concerne est le suivant:
9 fichiers:
fichier1: 2040,135742 Mo
fichier2: 396,4804688 Mo
fichier3: 1679,139648 Mo
fichier4: 3065,827148 Mo
fichier5: 908,6796875 Mo
fichier6: 3255,481445 Mo
fichier7: 251,6835938 Mo
fichier8: 2793,984375 Mo
fichier9: 3303,386719 Mo

Sachant qu'un DVD peut contenir 4483 Mo de données, on peut faire le petit calcul suivant: Somme des tailles / 4483 = 3.95.
On peut donc supposer qu'en la jouant fine, on pourrait peut-être tout faire rentrer sur 4 DVD. Je pense que c'est impossible mais j'aimerais un petit algo pour me le vérifier.

J'avais pensé tester toutes les combinaisons possibles, une combinaison par ligne où chaque colonne contient la taille d'un des fichiers, et par mes propres moyens ensuite (de façon assez simple avec Excel, en utilisant les fonctions somme et si), déterminer les fichiers à joindre sur chaque DVD.

Le problème est que je ne sais pas comment inscrire dans une feuille excel toutes les combinaisons, càd une par ligne.

Quelqu'un aurait-il une idée?

Merci d'avance et cordialement
François

 

[tototiti2008]

Re : optimisation du nombre de disques de gravure

Bonjour à tous,

trés intéressantes vos solutions

trés en retard :

PierreJean :

Le solveur qui a priori est une excellente methode s'avere ici un peu capricieux et ne donne pas toujours la meilleure reponse (voir fichier joint)

ta solution tient en 6 DVD, alors que le solveur en a trouvé 5, et si j'ai bien compris, le but est de minimiser le nombre de DVD ? Maintenant, il est clair que le solveur ne donne pas toujours de solutions excellentes, j'ai pu l'observer sur d'autres problèmes, mais bon là ça a l'air pas mal...

Renauder :

Ne connaissant pas le solveur, j'ai chargé ton fichier et j'ai voulu refaire la manip.
Il y a une chose que je n'arrive pas à faire c'est de mettre binaire à la contriante pour C13:I21. Il lui faut un chiffre ouune référence ou une formule ?

à priori, il lui faut une référence mais là aussi, j'ai remarqué sur d'autres problèmes que la contrainte binaire n'est parfois pas du tout respectée... comme ici il semblait me renvoyer que des 0 et 1, j'ai pas insisté, pour une fois qu'il la respecte

 

[pierrejean]

Re : optimisation du nombre de disques de gravure

Re

@tototiti

As-tu remarqué que dans mon dernier fichier j'avais porté le nombre de fichiers de 9 a 15 ?
En adaptant le solveur de ton fichier classeur1.xls a ces nouvelles valeurs j'ais du arreter le solveur a la branche 5000 apres quelques minutes (et il oscillait entre 6 et 7 DVD)
Peux-tu nous fournir le fichier qui avec ces valeurs trouve 5 DVD ?

 

[tototiti2008]

Re : optimisation du nombre de disques de gravure

Re,

Oups, désolé PierreJean, ce que j'ai ouvert c'était donc la démonstration de "non fonctionnement" du solveur (je ne peux pas ouvrir les zip)... Je sais qu'on avait également observé que le solveur, d'une version Excel à une autre, ne trouvait pas les mêmes solutions (parfois avec une version il trouvait une solution et avec une autre il n'en trouvait aucune...)
C'est un outil amusant mais pas toujours trés fiable, il semblerait...

 

[pierrejean]

Re : optimisation du nombre de disques de gravure

Re
Effectivement le solveur est un super instrument mais a manier avec beaucoup de prudence
dans ce cas le simple fait de presenter differemment l'ordre des fichiers fait qu'il donne un autre resultat
Quant a traiter 15 fichiers : la il pedale carrement dans la semoule
Pour que tu puisses apprecier mon dernier fichier et le tester (ca c'est mon point faible) le voila sans zip

 

[tototiti2008]

Re : optimisation du nombre de disques de gravure

Re,

eh, bien, ça c'est du code

voilà ce que m'a sorti le soveur en 1 minutes 30 à peu près :

à près tout, si tu cherches juste une solution, tu n'es pas préssé

je crois que je deviens flemmard, moi

 

[threepwood]

Re : optimisation du nombre de disques de gravure

Oups! Mille excuses, je n'avais pas vu qu'on m'avait répondu. En fait j'attendais d'être avertis par mail, l'erreur classique.

Je vais éplucher toutes les réponses et revenir en parler.

Merci d'avance pour vos contributions en tous cas.

 

[threepwood]

Re : optimisation du nombre de disques de gravure

Ça fait plaisir de voir l'intérêt porté a mon problème! Un grand merci a tous.

Je n'ai pas encore pris le temps d'étudier les réponses, mais j'ai cru noter que les solutions n'étaient pas nécessairement optimales. Si j'ai bien pigé (mais je n'ai pas encore regardé toutes les feuilles Excel aimablement proposées), les solutions sont le résultats de tirages stochastiques.

Ce que j'aimerais, c'est mettre dans une feuille Excel toutes les combinaisons possibles et inimaginables des 9 fichiers.
Mes souvenirs de cours de Maths de terminale étant un peu loin, je ne me souviens plus de l'opération mathématique consistant a calculer le nombre de combinaisons possibles lors d'un tirage sans remise, ou l'ordre importe.

Mais bon admettons que l'on souhaite recenser les "N" combinaisons de fichiers sur chaque ligne, ou chaque colonne indique un numéro de fichier, exemple:

1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 9 8
...

2 4 1 3 9 8 5 7 6
...
9 8 7 6 5 4 3 2 1

Si j'arrive a obtenir cela, je pourrai faire facilement une feuille Excel qui nous donne toutes les solutions minimales de nombre de DVD, feuille que je viendrai vous fournir ici.
Ainsi, j'obtiendrai toutes les solutions minimales, et non des solutions stochastiques.

Le probleme de base ici, c'est donc de faire une feuille Excel avec toutes les combinaisons, le découpage en DVDs étant une seconde étape du probleme, dont je connais déja la solution.

Quelqu'un pourrait m'indiquer comment faire pour obtenir toutes les combinaisons?

Merci beaucoup!

 

[threepwood]

Re : optimisation du nombre de disques de gravure

Bon, j'ai trouvé que la branche qui permet de compter les objets est l'analyse combinatoire. Et l'opération permettant de compter le nombre de combinaisons dans mon cas est la permutation sans répétition (voir pdf ).
Pour calculer le nombre de combinaisons, il faut utiliser la factorielle:
donc 9! = 362 880
Donc inutile de dire que mon idée de recenser toutes les possibilités est inapplicable!

 

[pierrejean]

Re : optimisation du nombre de disques de gravure

Re

Je crois que meme le recensement du nombre de combinaisons possibles est plus complexe !
En effet il ne s'agit pas de combiner 9 fichiers mais (en supposant que l'on ait un idée du resultat ce qui est raisonnable) de combiner 5 combinaisons de 1 a x fichiers avec pour optimums 1 fichier a valeur minimum et 4 fichiers dont la somme est inferieure a 4483
De façon pragmatique j'observe que la solution de MJ13 prob15(2) correspond a cette definition (sans garantie qu'il n'y en ait pas de meilleure puisqu'elle est apparement intuitive)
La solution de minick (adaptée aux 15 mêmes valeurs ne donne elle qu'un DVD minimum a 1000 alors que MJ13 trouve 751) . Je n'ai pas pu extraire l'algoritme du code pour savoir si la liste des solutions est exhaustive (353 a 6 DVD)
Quant a la mienne elle est fort loin avec mini a 2973 !!!
Le probleme n'a pas pour l'instant (a mon humble avis ) de solution garantie

 

[threepwood]

Re : optimisation du nombre de disques de gravure

Si, justement, j'ai ma petite idée la-dessus, faites-moi confiance ;-)

factorielle 9, c'est trop grand.
En revanche factorielle 8 = 40 320; c'est jouable dans Excel.

En partant du principe que le premier DVD contiendra le fichier no. 9, j'ai juste besoin d'une feuille Excel recensant, dans l'ordre du tirage (pour le moment on ne parle pas de nombre de DVD, juste d'un tirage successif d'éléments non remis), tous les arrangements possibles. Exemple de présentation qui me serait utile:

1 2 3 4 5 6 7 8
1 2 3 4 5 6 8 7
...et ainsi de suite...
8 7 6 5 4 3 2 1

DONC je change l'intitulé du problème:

Dans une urne, j'ai 8 boules numérotées de 1 a 8. Je les tire les unes après les autres sans les remettre dans l'urne. J'aimerais donc énumérer toutes les combinaisons de boules, dans l'ordre dans lequel elles ont été tirées. Il me faudrait une feuille Excel du type de ce que j'ai noté plus haut.

Quelqu'un serait-il capable de me générer une feuille Excel recensant les 40 320 possibilités?

Une fois cela en poche, ça résoudra mon problème, et je viendrai vous fournir ma feuille Excel résolvant mon problème de DVD, qui est la seconde partie du probleme. Mais une chose après l'autre

Bien entendu, ma solution est applicable pour 8 éléments. Au-delà, c'est l'explosion combinatoire et on doit faire absolument appel a une solution stochastique.

Merci pour votre aide! J'espère avoir vos contributions ;-)
Ça fait un excellent problème a résoudre, non?

Et puis par la même occasion ça permettra de vérifier la rigueur des précédents algorithmes que vous m'avez proposé, dans la mesure ou on aura a disposition la solution minimale vraie.

 

[pierrejean]

Re : optimisation du nombre de disques de gravure

Re

Si tu as 5 mn (temps mis par le PC de ma petite-fille ,le mien etant out en ce moment)

teste cette macro

Sub combin()
debut = Timer
Application.ScreenUpdating = False
Dim coll As Collection
Set coll = New Collection
ligne = 1
col = 1
For a = 1 To 8
 For b = 1 To 8
  For c = 1 To 8
   For d = 1 To 8
    For e = 1 To 8
     For f = 1 To 8
      For g = 1 To 8
       For h = 1 To 8
            For m = 1 To coll.Count
             coll.Remove 1
            Next m
           On Error Resume Next
             coll.Add a, CStr(a)
             coll.Add b, CStr(b)
             coll.Add c, CStr(c)
             coll.Add d, CStr(d)
             coll.Add e, CStr(e)
             coll.Add f, CStr(f)
             coll.Add g, CStr(g)
             coll.Add h, CStr(h)
             If Err.Number <> 0 Then pass = True
           On Error GoTo 0
          If pass Then
            pass = False
          Else
          Cells(ligne, col) = a & b & c & d & e & f & g & h
          ligne = ligne + 1
           If ligne = 411 Then
             ligne = 1
             col = col + 1
            End If
          End If
       Next
      Next
     Next
    Next
   Next
  Next
 Next
Next
Application.ScreenUpdating = True
MsgBox (Timer - debut)
End Sub

 

[pierrejean]

Re : optimisation du nombre de disques de gravure

Re

Et si tu n'as pas le temps voici les 40320 combinaisons

 

[threepwood]

Re : optimisation du nombre de disques de gravure

Re

Et si tu n'as pas le temps voici les 40320 combinaisons

Merci beaucoup pierrejean, ta feuille Excel m'a été d'un grand secours.
J'ai pu donc trouver les solutions minimales, et effectivement il me faut 5 DVD.
J'ai poussé un peu l'optimisation en cherchant parmis les solutions "5 DVD" celles qui me donnaient la place maximale restante sur l'un des DVD. Il s'avère qu'il existe environ 2400 combinaisons donnant la solution minimale.

Tu pourras trouver en pièce jointe une version "allégée" de ma feuille Excel, étant donné que la feuille entière zippée prenait 6Mo.

Merci a tous pour votre aide, je jetterai un œil sur vos algos, car je risque d'en avoir encore besoin a l'avenir pour d'autres applications.