# -*- coding: utf-8 -*-
# Created on Sat Sep 31 08:15:00 2024
# @author: mhebding
# TP2 - Programmation dynamique 2



## Le sac a dos

# 1.
None # donnees a implementer



## 1 - Programmation dynamique du probleme

# 2.
# Lorsque P=0, on ne peut plus mettre aucun objet dans le sac donc V(i,P)=0
# Lorsque i=0, il n'y a plus d'objets à mettre dans le sac donc V(i,P)=0

# 3.
# Deux choix à chaque fois : 
# 1) Prendre l’objet i. La capacité restante est alors P-pi
# la valeur maximale qu’on peut y rajouter, sachant qu’il nous reste les objets de 0 à i, est V(i-1,P-pi)
# Ainsi notre sac à dos aura une valeur totale de vi + V(i-1, P-pi).
# 2) Ne pas prendre l’objet i. La valeur maximale possible est alors V(i-1,P)
# La solution optimale est la meilleure (max) de ces deux là, d’où la formule.

# 4.
def matrice(lignes, colonnes, nombre):
	M = []
	for i in range(lignes):
		M.append([])
		for j in range(colonnes):
			M[i].append(nombre)
	return M

# 5.
def sacDynamique(poids, valeurs, capacite):
	N = len(poids)
	V = matrice(N+1, capacite+1 ,0)
	for p in range(1,capacite+1):
		for i in range(0,N):
			V[i+1][p] = max(V[i][p], V[i][p-poids[i]] + valeurs[i])
	return V, V[-1][-1] # ligne modifiée pour 9.

#print('Version Dynamique')
#print(sacDynamique(poids, valeurs, 8))

# 6.

# Les lignes correspondent au numéro de l'objet. 
# Les colonnes a la capacite du sac.
# Le dernier élément de la dernière ligne correspond à la valeur maximale.



## 2 - Reconstruction de la solution

# 7. 8.
def reconsruction(V, poids, valeurs, noms, capacite):
	i = len(poids)
	p = capacite
	objets = []

	while i > 0 and p > 0:
		if V[i][p] != V[i-1][p]:	# l objet i-1 a ete pris
			objets.append(noms[i-1])
			p -= poids[i-1]
		i -= 1
	return objets[::-1]



## 3 - Essais

# 9. 10.

# Essais a faire vous meme