Discussion :

[mikele]

Bonjour à tous!

J'ai cherché sur le forum, mais sans trouver de réponse...

Voilà l'énoncé de mon problème:
Imaginons que vous avez une série de sketchs ayant des durées différentes et que vous voulez ranger vos sketchs en épisodes de durée fixe. Comment vous vous y prendriez pour ranger les sketchs en épisodes ?

Quelques précisions:
- l'ordre des sketchs au sein d'un épisode n'est pas important.
- les épisodes doivent avoir autant que possible une durée uniforme.
- ( les épisodes sont plus longs que les sketchs )

Merci du coup de pouce si vous voulez bien vous y coller et à bientôt!

[Zavonen]

Il manque des contraintes:
Le nombre d'épisodes est-il fixe ?
La durée d'un épisode est-elle fixe ?

[Jedai]

Ca ressemble un peu à du bin packing, mais il nous manque effectivement quelques points, en particulier la durée des épisodes est-elle donnée d'office, ou le nombre d'épisode ? (Ces deux contraintes n'aboutissent pas au même problème)

--
Jedaï

[mikele]

Bonsoir et merci de vos réponses si rapides.

Le nombre d'épisode n'est pas fixe par contre leur durée est fixée et la même pour tous les épisodes.

[Jedai]

Ok, c'est du bin-packing alors, la mauvaise nouvelle étant que c'est du NP-Complet, la bonne étant qu'il y a des algorithmes simples qui donnent une réponse "pas trop mauvaise".

--
Jedaï

[mikele]

Je viens de mettre en place et de tester le bin packing qui donne des très bon résultats dans ce cas... 0 à -3 sec d'erreur.

Petite chose à savoir: la distribution de la longueur des sketchs influence énormément le remplissage des épisodes. En effet, suivant cette distribution, on peut se retrouver avec un épisode constitué d'un sketch très long et d'un sketch très court et d'autres épisodes contenant énormément de sketchs. Mais le tout avec des longueurs d'épisodes très homogènes.

Maintenant tout dépend si l'erreur sur la longueur d'un épisode est importante ou si c'est l'homogénéité des épisodes qui prime. Voilà! Si vous tombez sur un problème du même type... A bon entendeur!

En tout cas, merci à vous!