Algorithme de stockage dvd - Pour ceux qui aime résoudre des énigmes

Bonjour tlm !

Bon alors voila je cherche à creer un algorithme le plus efficace possible pour stocker des morceaux de film sur des DVD.

Tous mes morceaux de films sont stockés dans une base de données avec leur durée. Sachant qu’ils ont tous le meme format de compression, je me suis basé sur une constante de 1h30 de film par DVD.

Mon algorithme dois pouvoir me faire la liste des films à mettre dans chacun des DVD.

Je n’ai pas de limite de DVD ni d’ordre particulier à faire. Je veux juste optimiser de facon automatique le rangement des morceaux de films.

Si vous avez une idée, une piste, LE CODE COMPLET :), je suis preneur.

merci :wink:

Tu utilisera quel langage? quelle type de bd?

LE CODE COMPLET? non. Ca sera à toi de bosser. Ceci dit un DVD = 4.7 Go (à confirmer), une vidéo = XXX Mega, donc il te suffit juste de choisir un tuple de valeur tel que leur poids en mega soit égal à 4.7Go.

Au boulot!

Language PHP, base SQL. Mais je restranscris c’est pas un problème. C’est juste pour avoir une logique de conception. car la je seche un peu … :frowning:

Sinon pour des Films c’est au format MPEG2. Compréssé en 1500k. 2h de film par DVD me suffise :wink:

D’autre question ? et surtout des reponses ! :slight_smile:

Merci

Tous les films n’ont pas la meme taille… car il ne font pas dutout le meme temps. Ca peut aller de 15min à 1h30… Tu comprends ?

C’est une question de taille. C’est pas parce que sur les CD tu as écris 70 Minutes, que tu ne peux pas mettre 650 Mo hein.

Maintenant, je n’en sais pas plus sur le format de tes films (divx? etc)

Ca ne m’étonne pas de toi ca tiens :MDR

Les formats sont tous encodé en mpeg2 en 1500Kps. Donc etant donné que cette variable est constante, tu peux te baser sur le temps des videos pour calculer l’espace sur un DVD.

Sachant que je vois assez large keu meme.

Est ce que tu vas avoir un menu? Ou alors, c’est un DVD purement de données (pour PC/MAC) qui va juste contenir deux/trois fichiers qui constitueront tes vidéos?

Si oui, base toi sur les octets. Tu auras des calculs plus pertinents.

Pas de menu, juste des données, 2 3 fichiers par dvd aprioris.
Les octets, oui j’y penserais.

Je veux juste un algo qui m’optimise un rangement pour gacher le moins de place possible sur les DVD.

Merci

http://www.infop6.jussieu.fr/lmd/2004/lice…/cours2_fb4.pdf

:neutre:

Sympa ça !!!

Bon Mais le truc c’est que si j’ai 3 film :

1er : 1h00
2eme : 0h45min
3eme : 0h45min

Il fo qu’il essai aussi 2 avec 3. et pas 1 et 2 ou 1 et 3.

C’est pas évident, mais c’est une bonne piste. D’autres idées ?

L’idée de base :

Soient E l'ensemble des fichiers,
 F les fichiers déjà pris (<- ceux que tu prendras certainement)
Tant que taille < 4.7Go
  Prendre un fichier A tel que A = min(E)
  Si taille + taille(A) < 4.7Go
    Ajoute A à F (donc retire A de E)
    taille = taille + taille(A)
  Sinon
    Fin du travail (break)
  FinSi
FinTantQue

En bossant avec des octets, ça devrait le faire.

Bien sûr, c’est un algo. minimaliste : il colle tous les plus petits fichiers ensemble, et ainsi de suite.

Merci :wink: avec ca je devrai reussir à réaliser la pluspart de mes gravures :wink:
Je le code en php now :slight_smile:

Un exemple d’algo en c++
reste à coder les classe nécessaires et les fonctions associées

calc_films()
{
//film=tableau de films
x=nb_films (nombre de films)
longueur_min(taille mini d'un film)

while(x)//tant qu'il y a des films non ajoutés
{
	dvd=new dvd;
	for(int i(0);i<nb_film;i++)//boucle sur les films
  {
  if (film(i).utilise=0)//si le film n'est pas deja ajouté
  	{
  	if (film(i).duree<dvd.place_restante())
    {
    dvd.add(film(i));
    film(i).utilise=1;
    x--; //un film en moins
    }
  	}
  if (dvd.place_restante<longueur_min)break;
  }
	
	//le dvd est plein ou il n'y a plus de films
	dvd.affiche();
}	

}

Ton algo est pamal, mais il est en language objet. Or mon site est réalisé en PHP procédural.

Je vais donc m’orienter vers celui de sans-nom.

Merci bcp keu meme :wink:

koike apres relecture, il me semble plus logique dans la conception, prenant en compte tous la liste des dvd, et qu’il les compares à la taille du dvd en cours