##corrigé TP5
## exo 2
"""On distingue les trois cas :
- Si i = 0, aucun objet n’est placé dans le camion donc la valeur du chargement est 0.
- Si i > 0 et pi > w, on ne peut pas placer l’objet i dans le chargement car son poids dépasse le poids maximal w. Ainsi, il revient au même de chercher la valeur maximale
en considérant uniquement les i - 1 premiers objets.
- Si i > 0 et pi<=w, soit on maximise la valeur en prenant l’objet i (dans ce cas la valeur maximale vaut vi auquel on ajoute la valeur maximale obtenue avec les i - 1 premiers objets sachant que le poids maximal vaut maintenant w- pi), soit on maximise sans l’objet i (ce qui revient au point précédent). On choisit alors le maximum des deux
valeurs
"""

def recur(P,V,i,w):
    if i==0:
        return 0
    if P[i-1]>w:
        return recur(P,V,i-1,w)
    return max(recur(P,V,i-1,w), V[i-1]+recur(P,V,i-1,w-P[i-1]))

#test
P=[3,2,1,4]
V=[4,3,1,9]
Pmax=8
print(recur(P,V,4,Pmax))

##
n=len(P)
Memoire=[[-1 for j in range(Pmax+1)] for i in range(n+1)]
#ou
#Memoire=[[-1]*(Pmax+1)]*(n+1)#ATTENTION listes liées
#les arrays permettrait le calcul vectoriel, bcp plus rapide ...

def recur2(P,V,i,w,Memoire):
    if i==0:
        return 0
    if Memoire[i][w]>-1:
        return Memoire[i][w]
    if P[i-1]>w:
        Memoire[i][w]=recur2(P,V,i-1,w,Memoire)
        return Memoire[i][w]
    else:
        if Memoire[i-1][w]==-1:
            Memoire[i-1][w]=recur2(P,V,i-1,w,Memoire)
        if Memoire[i-1][w-P[i-1]]==-1:
            Memoire[i-1][w-P[i-1]]=recur2(P,V,i-1,w-P[i-1],Memoire)
        a=max(Memoire[i-1][w],V[i-1]+Memoire[i-1][w-P[i-1]])
        Memoire[i][w]=a
        return Memoire[i][w]

#test
P = [5,3,3,3];
V = [4,3,1,1];
Pmax = 8;

print(recur2(P,V,n,Pmax,Memoire))

##
import random as rd
import time as t
P=[rd.randint(1,100) for i in range(40)]
V=[rd.randint(1,100) for i in range(40)]
Pmax=200

d=t.time()
print(recur(P,V,len(P),Pmax))
f=t.time()
print("recur = ",f-d)

n=len(P)
Memoire=[[-1 for j in range(Pmax+1)] for i in range(n+1)]
d=t.time()
print(recur2(P,V,len(P),Pmax,Memoire))
f=t.time()
print("recur2 = ",f-d)