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.
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.
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.
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.
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.
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();
}
}
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