# ================================================================================================
# Ce programme permet de comparer l'algorithme glouton et la force brute
# pour le problème de sac à dos en créant une liste aléatoire
# de 15 vidéos afin de répondre à la question suivante :
#
# Quelle est la paobabilité pour que la solution optimale ne soit pas une des 3 solutions gloutone ?
#
# nsi.gecif.net
# Décembre 2025
# ================================================================================================

from random import *

# =============================================================
# Fonctions du problème du sac à dos pour la force brute :

def int_to_bin(n, nb):
    """ n et nb sont de type int
    n est le nombre à convertir en binaire
    nb est le nombre de bits utilisés """
    ch = ""
    while n > 0:
        r = n % 2
        n = n // 2
        ch = str(r) + ch
    ch = (nb - len(ch)) * "0" + ch
    return ch

def ens_des_parties(ensemble):
    """ ensemble est une liste de p-uplets """
    nb = len(ensemble) # nombre d'éléments
    n = 2 ** nb # nombre de parties
    parties = [] # l'ensemble des parties
    for i in range(1, n):
        ch = int_to_bin(i, nb) # écriture de i sur nb bits
        partie = [] # construction d'une partie
        for j in range(len(ch)):
            if ch[j] == "1":
                partie.append(ensemble[j])
        parties.append(partie) # la partie construite est ajoutée à la liste
    return parties

def duree_totale(liste):
    d = 0
    for triplet in liste:
        d += triplet[1]
    return d

def taille_totale(liste):
    t = 0
    for triplet in liste:
        t += triplet[2]
    return t

def recherche(ens_parties, contrainte):
    duree_max = 0
    solution = []
    for partie in ens_parties: # un choix possible de fichiers
        duree = duree_totale(partie)
        taille = taille_totale(partie)
        if taille <= contrainte and duree > duree_max:
            duree_max = duree
            solution = partie
    return solution, duree_max


def force_brute(fichiers, taille_max):
    parties = ens_des_parties(fichiers)
    return recherche(parties, taille_max)

# =============================================================
# Fonction du problème du sac à dos pour l'algorithme glouton :

def duree(fichier):
    return fichier[1]

def taille(fichier):
    return 1 / fichier[2]

def rapport(fichier):
    return fichier[1] / fichier[2]

def glouton(liste, taille_max, choix):
    triee = sorted(liste, key=choix, reverse=True)
    reponse = []
    totale_duree = 0
    taille = 0
    i = 0
    while i < len(liste) and taille <= taille_max:
        nom, d, t = triee[i] # nom, durée et taille
        if taille + t <= taille_max:
            reponse.append(nom)
            taille += t
            totale_duree += d
        i += 1
    return reponse, totale_duree

# =============================================================
#  Programme principal
# =============================================================

# les 7 vidéos d'origine :
"""videos = [('Video 1', 114, 4.57), ('Video 2', 32, 0.630),
('Video 3', 20, 1.65), ('Video 4', 4, 0.085),
('Video 5', 18, 2.15), ('Video 6', 80, 2.71),
('Video 7', 5, 0.320)]"""

# création d'une liste de vidéos aléatoires (liste de tuples) :
videos=[]
for num in range(1,16):
    t=('Video '+str(num),randint(2,10),randint(200,1000)/100)
    videos.append(t)

print("Liste des vidéos :")
print(videos)

taille_max=25

print("\nRésultats des 3 algorithmes gloutons :")
# Affichage complet :
"""print("Glouton d'après la durée :",glouton(videos, taille_max, duree))
print("Glouton d'après la taille :",glouton(videos, taille_max, taille))
print("Glouton d'après le rapport durée/taille :",glouton(videos, taille_max, rapport))"""
# Affiche seulement la durée totale :
print("Glouton d'après la durée :",glouton(videos, taille_max, duree)[1])
print("Glouton d'après la taille :",glouton(videos, taille_max, taille)[1])
print("Glouton d'après le rapport durée/taille :",glouton(videos, taille_max, rapport)[1])

choix = force_brute(videos, taille_max)
duree_totale = choix[1]
choix_fichiers = [fichier[0] for fichier in choix[0]]
# Affichage complet :
"""print("\nRésultat optimal donné par la force brute : ",choix_fichiers, duree_totale)"""
# Affiche seulement la durée totale :
print("\nRésultat optimal donné par la force brute : ",duree_totale)