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



## 1 - Methode gloutonne

# 1. 
None # Reponse a la question 1. en commentaire

# 2. 
None # Reponse a la question 2. en commentaire

# 3. 
None # Reponse a la question 3. en commentaire

# 4. 
None # Arbre de decisions a faire sur papier

# 5.
euros = [100, 50, 20, 10, 5, 2, 1]

def rendu_glouton(systeme, somme):
	return None

#print('Essai glouton')
#print(rendu_glouton(euros,16))



## 2 - Methode recursive

# 6.
from math import inf

# Pseudo-code
# def rendu_recursif(systeme,somme):
#	si somme<0 alors
#		return infini
#	sinon si somme=0 alors
#		return 0
#	minimum <- infini
#	pour x dans systeme faire
# 		si somme>=0 alors
#			minimum <- min(minimum,1+rendu_recursif(systeme,somme-x))
#	return minimum

def rendu_recursif(systeme, somme):
	return None

#print('Essai recursif')
#print(rendu_recursif(euros,16)) # trop long a executer pour 48



## 3 - Methode avec memoisation

# 7.
def rendu_memoise(systeme, somme):
	return None # version qui renvoie f[somme]

# 8.
def rendu_memoise2(systeme, somme):
	return None # version qi renvoie f

#print('Essai memoise')
#print(rendu_memoise(euros,16))
#print(rendu_memoise2(euros,16))

None # Reponse a la question 8. en commentaire

# 9. 
None # Reponse a la question 9. en commentaire

# 10. 
None # Arbre de decisions a faire sur papier



## 4 - Reconstitution de solution

# 11. 
def rendu_memoise_reconstitue(systeme, somme):
	f = [0] * (somme + 1) # commentaire ?
	g = [0] * (somme + 1) # commentaire ?
	for s in range(1, somme + 1):
		f[s] = inf # commentaire ?
		for x in systeme:
			if s >= x:
				if 1 + f[s - x] < f[s]:
					f[s] = 1 + f[s - x] # commentaire ?
					g[s] = s - x        # commentaire ?
	monnaie = []
	while somme > 0:
		monnaie.append(somme - g[somme]) # commentaire ?
		somme = g[somme]
	return monnaie

#print('Essai reconstitution')
#print(rendu_memoise_reconstitue(euros,16))