#################################################################################
#                                                                               #
#         2025-2026 : PC : corrigé du TP 3 d'informatique                 #
#                                                                               #
#################################################################################

rho = [16, 5, 8, 2, 5]
v = [2500, 800, 950, 200, 400]    #Pour les tests...



##Question 1:
def rapport_valeur_poids(v,p):
    L=[]
    for i in range(len(v)):
       L.append(v[i]/p[i])
    return L


##Question 2:
Pris = [False for k in range(len(v))]


def meilleur_objet_restant(pris,A):
    maxi=0 # Ici ça marche car les éléments de A sont supposés >0
    res = -1
    for i in range(len(A)):
        if not pris[i] and A[i] > maxi:
            maxi=A[i]
            res = i
        return res
##Question 3:
def meilleur_objet_restantMieux(pris , A, rho , c_restant): # Changement ici
    maxi=0
    res = -1
    for i in range(len(A)):
        if not pris[i] and A[i] > maxi and rho[i] <= c_restant : # Changement ici
            maxi=A[i]
            res = i
    return res

##Question 4:
def glouton(v, p, c):
    n = len(v)
    B = rapport_valeur_poids (v, p)
    pris = [ False for i in range (0,n)]
    res = []
    c_restant = c
    fini = False
    S=0
    while not fini :
        i = meilleur_objet_restantMieux(pris , B, p, c_restant)
        if i != -1 :
            res.append(i)
            pris[i] = True
            c_restant -=p[i]
            S += v[i]
        else:# Plus d'objet , ou l'objet restant est trop lourd.
            fini = True
    return res, S

##Question 5:
#Ici, l'invariant de boucle est le nombre d'objets non encore pris. C'est un entier positif, et à chaque
#itération de la boucle (sauf la dernière) il diminue de 1.
#On pourrait aussi utiliser la capacité restante du sac.

##Question 6:
#Notons d'abord que l'appel à la fonction rapport_poids_valeur n'utilise pas de comparaisons (si on
#veut sa complexité, on peut par exemple prendre en compte les divisions : il y en a n. Ceci est de
#toute façon négligeable devant la complexité de ce qui suit).
#La boucle principale est exécutée n fois. Et à chaque itération, elle utilise meilleur0bjetRestant qui
#coûte n comparaisons.
#Au total, nous avons n^2 comparaisons.

##Question 7:
#L'idée est de trier les objets par ordre décroissant de rapport valeur/poids. Il suffira alors de les
#prendre les uns après les autres tant qu'il y a de la place dans le sac. Ceci pourra être fait en une
#seule boucle for, donc en O(n) comparaisons.
#On rajoute à ceci le coût du tri (on choisit le tri implémenté dans la fonction sorted qu a un coût en
#O(n*log n) comparaisons) : cela fait O(n*log n)+O(n) soit O(n*log n) opérations.
#Détail technique : il ne suffit pas de trier le tableau alpha car alors on ignorerait à quel objet
#correspond chaque rapport. On est donc amené à créer un tableau de couples (rapport valeur/poids
#de l'objet i, i ).
#Comme Python, lorsqu'il compare deux couples, compare d'abord la première composante, la
#fonction sorted triera bien ce tableau selon le rapport valeur/poids.
def glouton_rapide(v, p, c):
    n=len(v)
    B = [ (v[i]/ p[i], i) for i in range(n) ]
    B_trié = sorted(B)
    c_restant = c
    res = []
    for k in range(n-1,-1,-1): # on lit à l'envers car les objets prioritaires sont en fin de liste
        i, ii =B_trié[k]
        if p[ii] <= c_restant:
            c_restant -= p[ii]
            res.append(ii)
    return res

##Question 8:
#Pour prendre en défaut l'algorithme glouton, on peut par exemple prendre un sac à dos de capacité
#8, et trois objets de poids 5 , 4, et 4, de valeurs respectives 11,8 et 8. L'algorithme glouton, à partir
#de la liste alpha, mettra uniquement l'objet de poids 5 dans le sac à dos pour une valeur totale de 11,
#alors qu'y placer les deux objets de poids 4 donne une valeur du sac de 16 .

##Question 9:
#Lorsque C=0 on ne peut rien mettre dans le sac (les poids sont supposés strictement positifs) donc
#V(C, i)=0.
#Lorsque i=0, l'ensemble {0... i-1} des objets possibles est vide, donc V(C, i)=0.

#Question 10:
#Pour remplir notre sac à dos de capacité C avec des objets de {0... i}, il y a deux choix :
#- soit prendre l'objet i. La capacité restante est alors C-r[i], et la valeur maximale qu'on peut y
#rajouter, sachant qu'il nous reste les objets de {0... i} est V(C-r[i], i-1). Ainsi notre sac à dos aura
#une valeur totale de V(C-r[i], i-1)+v[i].
#- soit ne pas prendre l'objet i. La valeur maximale possible est alors V(C, i-1).
#La solution optimale est la meilleure de ces deux-là, d'où la formule.

## Question 11
import numpy as np
def sacÀDosDyna(c0,v,p):
    n=len(p)
    V= [[0 for i in range(n+1)] for j in range(c0+1) ]
    for c in range(1,c0+1): # la ligne pour c==0 contient déjà des 0, inutile de la remplir.
        for i in range(0,n):
            if p[i] <= c:
                V[c][i+1]=max(V[c][i],V[c-p[i]][i]+v[i])
            else:
                V[c][i+1]=V[c][i]
    print(np.matrix(V))
    return V[c0][n]

## Question 12
#Comptons par exemple le nombre de max utilisés. Il y en a c0 × 𝑛.
#Pour la méthode naïve : le nombre d’ensembles d’objets possibles est 2^n (nombre de parties d’un ensemble
#à n éléments). Il aurait
#donc fallu 2^n − 1 comparaisons pour obtenir la valeur maximale, c’est beaucoup plus que par la méthode
#proposée ci-dessus.

## Question 13
def reconstruction(V, p, v):
    res =[]
    c=len(V) -1
    i=len(V[0]) -1 # c,i : case actuelle dans V
    res =[]
    while c>0 and i >0 :
        if V[c][i] == V[c][i-1] : #on n'a pas pris l'objet i-1
            i=i-1
        elif V[c][i] == V[c-p[i -1]][i-1] + v[i-1] : # on a pris l'objet i-1
            res.append(i-1)
            c=c-p[i-1]
            i=i-1
    return res

## Question 14
#Réponse : oui. Et même beaucoup.

## Question 15
def sac_à_dos_mémo(c0 , v, p):
    n = len(v)
    V = [[0 for i in range(0,n+1)] for j in range(0,c0+1) ] # -1 signifiera « case pas encore remplie »
    # Initialisation : mettre des 0 dans la première ligne et la première colonne
    for i in range(n+1):
        V[0][i]=0
    for c in range(c0+1):
        V[c][0]=0

    def aux(c, i):
    # Renvoie V(c,i) et remplit la case correspondante de V si elle ne l'était pas encore
        if c<=0:
            return 0
        elif V[c][i] != -1:
            return V[c][i]
        else:
            res = max( aux(c,i-1), aux(c-p[i-1], i-1) + v[i-1] ) # Attention , on utilise la formule précédente pour i-1 au lieu de i
            V[c][i] = res
            return res

    return aux(c0 , n), V

dico={}
def sac_a_dos_memo2(c0,i,v,p):
    n=len(v)
    for j in range(n+1):
        dico[(0,j)]=(0,[])
    for c in range(c0+1):
        dico[(c,0)]=(0,[])
    K=dico.keys()
    if (c0,i) in K:
        return dico[(c0,i)]
    else:
        if p[i-1]>c0:
            return dico[(c0,i-1)]
        else:
            a=sac_a_dos_memo2(c0,i-1,v,p)[0]
            L=sac_a_dos_memo2(c0,i-1,v,p)[1]
            b=v[i-1]+sac_a_dos_memo2(c0-p[i-1],i-1,v,p)[0]
            M=sac_a_dos_memo2(c0-p[i-1],i-1,v,p)[1]
            if a>b:
               dico[(c0,i)]=(a,L)
            else:
               M.append(i)
               dico[(c0,i)]=(b,M)
        return dico[(c0,i)]