## Corrige DS Mines 025
##################################

#Q1
"""
SELECT idC, val/taille as ratio
FROM Conteneurs
WHERE portDepC="Marseille" and portDestC="Barcelone" and dateDisp<2025-01-01
ORDER by ratio DESC
"""

#Q2 # Question pas claire...normal Bdd !
"""
SELECT idN, COUNT(IdC)
FROM Conteneurs
Groupe by idN
"""

#Q3
def profit(obj,S) :
    somme = 0
    for i in range(len(S)) : # Il faut parcourir la liste S pour savoir si l'objet est pris'
        somme += S[i]*obj[i][1] # Récupération du profit
    return somme

def profit2(obj,S) :
    somme = 0
    for i in range(len(S)) : # Il faut parcourir la liste S pour savoir si l'objet est pris'
        somme += int(S[i]*obj[i][1] # Récupération du profit
    return somme

#Q4
def contrainte (obj,S,b) : # Même structure que Q1
    somme = 0
    for i in range(len(S)) :
        somme +=S[i]*obj[i][0]
    return somme<=b

#Q5
b = [1,1,0] # Gauche,gauche, droite
c = [1,0,1] # Gauche,droite, gauche

#Q6
# Chaque objet pouvant être pris ou non, il y a 2 possibilités par objets soit 2**n combinaisons

# Il faut evaluer pour chaque combinaison les fonctions profit et contrainte, ce qui donne une compléxité de la forme n.2**n. La complexité est exponentielle, on ne peux donc pas traiter le problème par force brute.

#Q7 :
# les ratio sont 1.5, 4,1
# Il faut en premier choisir l'objet 1, il reste 4 en taille, puis l'objet 0, il reste 2 en taille, l'objet 2 ne peut-être choisi. Le profit est dans ce cas est de 7.

#Q8 :
#Ligne 5: Etape 1 : Lqi.append(obj[i][1]/obj[i][0])
#Ligne 12 : Li[j] = Li[j-1]
#Ligne 15 : Li[j] = i

obj = [(2,3),(1,4),(4,4)]
b = 5

def construitLi(obj) :
    Lqi = []
    Li = []
    for i in range(len(obj)) : # Etape 1
        Lqi.append(obj[i][1]/obj[i][0])
        Li.append(i)
    for i in range(1,len(Lqi)) : # Etape 2
        x = Lqi[i]
        j = i
        while j>0 and Lqi[j-1]<x :
            Lqi[j] = Lqi[j-1] # On fait glisser l'objet vers la droite
            Li[j] = Li[j-1]
            j-=1
        Lqi[j] = x # On replace l'objet mis de coté
        Li[j] = i
    return Li

#Q9 :
# Il s'agit ici d'un tri par insertion
# Le meilleur des cas est celui où on ne rentre jamais dans la boucle while, c'est celui où la liste est déja triée dans l'ordre décroissant. La compléxité est dans ce cas o(n) car la boucle for des lignes 4 à 6 sont de complexité o(n) ainsi que le boucle for de la ligne 7 car la complexité de la boucle while est o(1).
# Le pire des cas est alors la liste triée dans l'ordre coissant. Dans ce cas la bouche while est de compexité o(n) ce qui donne une complexité en o(n**2)

#Q10

S = len(obj)*[0]
Li = construitLi(obj)
j = 0
while j<len(S) and b > 0 : # Il faut soit parcourir tout les objets, soit le sac est plein
    if obj[Li[j]][0] <=b : # Il y a assez de place pour l'objet
        S[Li[j]] = 1 # On prend l'objet
        b = b - obj[Li[j]][0] # On diminue l'espace disponible
    j+=1

# Q11 :
# les ratio sont 1.5, 4,1
# Il faut en premier choisir l'objet 1, il reste 4 en taille, puis l'objet 0, il reste 2 en taille, l'objet 2 ne peut-être choisi. Le profit est dans ce cas est de 7.
# Le profit aurait pu être de 8 en choisissant l'objet 1 et 2. L'approche gloutone donne un optimum mais qui n'est pas forcement global.
b = 5
#Q12
def KPprogDynamique(obj,b) :
    T=[]
    n = len(obj)
    for k in range(n+1) : # Les lignes suivantes permettent de faire un tableau de 0 de dimension (n+1).(b+1)
        L = []
        for r in range(b+1) :
            L.append(0)
        T.append(L)
    for i in range(n) :
        for r in range(b+1) :
            if obj[i][0]<=r :
                T[i+1][r] = max(T[i][r],T[i][r-obj[i][0]]+obj[i][1])
                # On compare le profit entre les cas : On ne selectionne pas l'objet et on selection l'objet
            else :
                T[i+1][r] = T[i][r]
    #return T[n][b]
    S = n*[0] # Initialisation de S
    k = n-1
    r = b # Reste en taille
    while r>0 and k>=0 and T[k+1][r]!=0 :
        while k>0 and T[k+1][r]==T[k][r] : # Detection du changement de valeur par colonne
            k-=1
        S[k]=1
        r = r-obj[k][0]
        k-=1
    return S,T[n][b]




"""
[[0, 0, 0, 0, 0, 0],
 [0, 0, 3, 3, 3, 3],
 [0, 4, 4, 7, 7, 7],
 [0, 4, 4, 7, 7, 8]]"""

# La valeur est celle du profit maximal



#Q14
# Initialement S = [0,0,0], k = 2, r = 5
# Itération 1 : ligne 9 non vérifiée donc S = [0,0,1], k = 1, r = 1
# Itération 2 : ligne 9 non vérifiée donc S = [0,1,1], k = 0, r = 0
# Fin

#Q15 : Non car de complexité linéaire, dans le pire des cas k varie de n-1 à 0. o(n)

def construireArbreBinaire(a,n) :
    if n == 0 : return a
    else :
        filsGauche={'S' : a['S']+[1],'g':{},'d':{}}
        filsDroit={'S' : a['S']+[0],'g':{},'d':{}}
        a['g'] = filsGauche
        a['d'] = filsDroit
        construireArbreBinaire(filsGauche,n-1)
        construireArbreBinaire(filsDroit,n-1)

n=3
arbreSol = {'S':[],'g':{},'d':{}}
construireArbreBinaire(arbreSol,3)

#Q15
def estFeuille(a) :
    return a['g']=={} # Il suffit de regarder si un des 2 fils est vide.

global Pmin
Pmin = 7
#Q16
def possible(obj,Sk,b) :
    S0 = Sk + [0]*(len(obj)-len(Sk)) # Nombre de 0 manquants
    S1 = Sk + [1]*(len(obj)-len(Sk)) # Nombre de 1 manquants
    return contrainte(obj,S0,b) and profit(obj,S1)>Pmin # Il faut restreindre le nombre d'objet


def KPforceBrute(arbre,obj,b) :
    global Pmin,Sol
    if estFeuille(arbre) :
        if contrainte(obj,arbre['S'],b) :
            P=profit(obj,arbre['S'])
            if P > Pmin :
                Pmin = P
                Sol = arbre['S']
    else :
        KPforceBrute(arbre['g'],obj,b)
        KPforceBrute(arbre['d'],obj,b)

#Q17 : Elager revient à ne pas explorer la branche si les critères ne sont pas reunies

def KPpse(arbre,obj,b) :
    global Pmin,Sol
    if estFeuille(arbre) :
        if contrainte(obj,arbre['S'],b) :
            P=profit(obj,arbre['S'])
            if P > Pmin :
                Pmin = P
                Sol = arbre['S']
    else :
        if possible(obj,arbre['g']['S'],b) :
            KPpse(arbre['g'],obj,b)
        if possible(obj,arbre['d']['S'],b) :
            KPpse(arbre['d'],obj,b)

rho=0.8
Tmax=6
Tmin=0.01

def mettreAjourTetSolution(obj,T,S):
    global SbestOfAll,PbestOfAll
    # 2)c)i.
    for k in range(len(T)) :
        T[k] = rho*T[k]
    # 2)c)ii.
    Pmax,kmax = profit(obj,S[0]),0
    for k in range(len(S)) :
        if profit(obj,S[k]) > Pmax :
            Pmax,kmax = profit(obj,S[k]),k
    # 2)c)iii.
    if Pmax>PbestOfAll:
        PbestOfAll=Pmax
        SbestOfAll=S[kmax]
    #2)c)iv.v.vi.
    qte = 1 / (1 + PbestOfAll - Pmax) # Calcul de la quantite
    for elt in range(len(S[kmax])) :
        if S[kmax][elt]==1 : # Pour chaque objet de Smax choisi
            T[elt]+=qte # Ajout de la quantité
        if T[elt] < Tmin : # Respect des regles sur les taux
            T[elt] = Tmin
        if T[elt] > Tmax :
            T[elt] = Tmax

nbit = 100
nbAnts = 1
alpha=2
beta=5

from random import randint,random

def miseAjourCandidats(obj:[(int)],candidats:[int],b:int) :
    k = 0
    while k < len(candidats) :
        if obj[candidats[k]][0]>b2 :
            candidats.remove(candidats[k])
            k-=1
        k+=1


def construitProb(obj,candidats,b,T):
    m=len(candidats)
    prob= {} # Dictionnaire vide pour la structure de donnee
    for i in range(m):
        oi=candidats[i]
        prob[oi] = (T[oi]**alpha) * (b*obj[oi][1]/obj[oi][0])** beta
    s=sum(prob.values())
    for i in range(m):
        oi=candidats[i]
        prob[oi] = prob[oi]/s
    return prob


def choixCandidat(candidats,prob) :
    p = random()
    s = 0
    for c in candidats :
        s+=prob[c]
        if p<s :
            return c
    return c

obj = [(78, 45), (92, 72), (89, 33), (11, 84), (92, 3), (88, 69), (16, 76), (13, 68), (85, 2), (76, 13), (16, 74), (77, 55), (63, 30), (35, 20), (10, 77), (60, 22), (76, 68), (58, 19), (88, 49), (11, 98)]
b = 200
#1)a)
n=len(obj)
T=[Tmax for i in range(n)]
#1)b)
PbestOfAll=0
SbestOfAll=n*[0]
#2)
for it in range(nbit):
    #2)a)
    S=[n*[0] for i in range(nbAnts)]
    #2)b)
    for k in range(nbAnts):
        b2=b
        #2)b)i.
        o0 = randint(0,n-1) # Choix d'un objet aléatoire
        #2)b)ii.
        S[k][o0] = 1 # Choix de l'objet o0
        b2 -= obj[o0][0] # Retrait dans la place disponible
        #2)b)iii.
        candidats=[i for i in range(n) if i!=o0]
        miseAjourCandidats(obj,candidats,b2)
        #2)b)iv.
        while b2>0 and candidats!=[ ]:
            prob = construitProb(obj,candidats,b2,T) # Construire les probas
            o1 = choixCandidat(candidats,prob) # Choix du candidats
            S[k][o1] = 1 # Indique que l'objet o1 a été choisi
            b2-= obj[o1][0] # Retrait dans la place disponible
            candidats.remove(o1) # Enlever o1 de la liste des candidats
            miseAjourCandidats(obj,candidats,b2) # Mettre à jour les candidats en fonction de la place restante

        mettreAjourTetSolution(obj,T,S)

# Generation d'un test
obj2 = []
for k in range(20) :
    obj2.append((randint(1,100),randint(1,100)))

obj2 = [(78, 45), (92, 72), (89, 33), (11, 84), (92, 3), (88, 69), (16, 76), (13, 68), (85, 2), (76, 13), (16, 74), (77, 55), (63, 30), (35, 20), (10, 77), (60, 22), (76, 68), (58, 19), (88, 49), (11, 98)]

b = 200
S = len(obj2)*[0]
Li = construitLi(obj2)
j = 0
while j<len(S) and b !=0 : # Il faut soit parcourir tout les objets, soit le sac est plein
    if obj[Li[j]][0] <=b : # Il y a assez de place pour l'objet
        S[Li[j]] = 1 # On prend l'objet
        b = b - obj[Li[j]][0] # On diminue l'espace disponible
    j+=1