#Q1
def glouton(c, poids, val):
    """glouton(c : int, poids : list, val : list) -> int
        Renvoie la valeur maximum qu'on peut obtenir avec les objets
        ordre: liste des objets
        entrees :   c, entier, capacité du sac
                    poids, liste de nombres  comportant le poids des objets
                    val, liste de nombres comportant la valeur des objets
        sorties: valeur, nombe, la valeur maximale que l'on peut emporter
    """
    poids_max = 0
    valeur = 0
    for i in range(len(poids)):
        if poids_max + poids[i] <= c:
            poids_max += poids[i]
            valeur += val[i]
    return valeur

print( glouton(10, [5, 3, 6], [4, 4, 6])) # renvoie 8

#Q2
def combine(L1, L2):
    """ combine(L1:list, L2:list) -> list
        entrees : L1,L2, deux listes de nombres de même longueur
        sorties : L, liste de tuples 
    """
    L = []
    for i in range(len(L1)):
        L.append((L1[i], L2[i]))
    return L
print ( combine([1, 2, 3], [4, 5, 6])  ) # [(1, 4), (2, 5), (3, 6)]

#Q3
def split(L):
    """ split(L:list) -> list, list
        entrees : L, liste de tuples 
        sorties : L1,L2, listes de nombres de même longueur
    """
    L1 = []
    L2 = []
    for i in range(len(L)):
        L1.append(L[i][0])
        L2.append(L[i][1])
    return L1, L2
#Q4
def tri_poids(poids, val):   
    """ tri_poids(poids:list, val:list) -> list
        entrees : poids,val, listes 
        sorties : 2 listes triées de même longueur, la 1e liste est triée par poids croissant
    """
    L = combine(poids, val)
    L.sort()
    return split(L)
tri_poids([5, 3, 6], [42, 0, 2]) #([3, 5, 6], [0, 42, 2])

#Q5
def glouton_poids(c, poids, val):
    poids, val = tri_poids(poids, val)
    return glouton(c, poids, val)
glouton_poids(10, [5, 3, 6], [4, 4, 10])   #retourne 8

#Q6
def tri_valeur(poids, val):
    """ def tri_valeur(poids:list, val:list) -> list
        entrees : poids,val, listes 
        sorties : 2 listes triées de même longueur, la 2e liste est triée par valeur decroissant
    """
    L = combine(val, poids)
    L.sort(reverse=True)
    L1, L2 = split(L)
    return L2, L1

def glouton_valeur(c, poids, val):
    poids, val = tri_valeur(poids, val)
    return glouton(c, poids, val)
glouton_valeur(10, [5, 4, 7], [4, 4, 6]) # retourne 6
#Q7
def tri_ratio(val, poids):
    L = combine(val, poids)
    L = combine([val[i]/poids[i] for i in range(len(val))], L)
    L.sort(reverse=True)
    return split(split(L)[1])

def glouton_ratio(c, poids, val):
    val, poids = tri_ratio(val, poids)
    return glouton(c, poids, val)
glouton_ratio(10, [5, 4, 7], [4, 4, 6]) #8


def prog_dyn(c, poids, val):
    """prog_dyn(c : int, poids : list, val : list) -> int
        Renvoie la valeur maximale qu'on peut obtenir avec les objets
        entrees :   c, entier, capacité du sac
                    poids, liste de nombres  comportant le poids des objets
                    val, liste de nombres comportant la valeur des objets
        sorties: valeur, nombe, la valeur maximale que l'on peut emporter
    """
    n = len(poids)
    dp = [[0 for j in range(c+1)] for i in range(n+1)]
    #print(dp)
    for i in range(1, n+1):
        for j in range(1, c+1):
            if j < poids[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-poids[i-1]] + val[i-1])
        #print(dp)
    return dp[n][c]
prog_dyn(10, [5, 4, 7], [4, 4, 6])# retourne 8


import random

def genere_instance():
    c = random.randint(1, 1000)
    poids = [random.randint(1, 100) for i in range(100)]
    val = [random.randint(1, 100) for i in range(100)]
    return c, poids, val


gp, gv, gr = 0, 0, 0
for i in range(100):
    c, poids, val = genere_instance()
    sol = prog_dyn(c, poids, val)
    gp += glouton_poids(c, poids, val)/sol
    gv += glouton_valeur(c, poids, val)/sol
    gr += glouton_ratio(c, poids, val)/sol
print(f"Glouton poids : {gp/100}")
print(f"Glouton valeur : {gv/100}")
print(f"Glouton ratio : {gr/100}")


import time
t1, t2 = 0, 0
for i in range(100):
    c, poids, val = genere_instance()
    t = time.time()
    glouton_poids(c, poids, val)
    t1 += time.time() - t
    t = time.time()
    prog_dyn(c, poids, val)
    t2 += time.time() - t
print(f"Glouton poids : {t1} s")
print(f"Programmation dynamique : {t2} s")


def prog_dyn(c, poids, val):
    n = len(poids)
    dp = [[0 for j in range(c+1)] for i in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, c+1):
            if j < poids[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-poids[i-1]] + val[i-1])

    # reconstruction de la solution
    i, j = n, c
    sol = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            sol.append(i-1)
            j -= poids[i-1]
            i -= 1
    return sol
print( prog_dyn(10, [5, 4, 7], [4, 4, 6]) )
# la solution optimale consiste à choisir les objets 1 et 0 [1, 0]