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



## 1 - Methode gloutonne

# 1. 
# On rends 10 cts et il reste 1, impasse

# 2. 
# On peut rendre 5 + 2 + 2 + 2, la somme exacte avec 4 pieces

# 3. 
# La solution gloutonne donne une solution, non exacte ni optimale

# 4. 
# Arbre de decisions a faire sur papier

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

def rendu_glouton(systeme, somme):
	i = 0
	p = len(systeme)
	monnaie = []
	while i<p and somme>0:
		if systeme[i]>somme:
			i += 1
		else:
			monnaie.append(systeme[i])
			somme -= systeme[i]
	if somme == 0:
		return monnaie
	else:
		return None

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



## 2 - Methode recursive

# 6.
from math import inf

def rendu_recursif(systeme, somme):
	if somme < 0:
		return inf
	elif somme == 0:
		return 0
	mini = inf
	for x in systeme:
		if somme >= x:
			mini = min(mini, 1 + rendu_recursif(systeme, somme - x))
	return mini

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



## 3 - Methode avec memoisation

# 7.
def rendu_memoise(systeme, somme):
	f = [0] * (somme + 1)
	for s in range(1, somme + 1):
		f[s] = inf
		for x in systeme:
			if s >= x:
				f[s] = min(f[s], 1 + f[s - x])
	return f[somme]

# 8.
def rendu_memoise2(systeme, somme):
	f = [0] * (somme + 1)
	for s in range(1, somme + 1):
		f[s] = inf
		for x in systeme:
			if s >= x:
				f[s] = min(f[s], 1 + f[s - x])
	return f

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

# f(16) : il s'agit du nombre minimum de pièce à utiliser pour rendre 16 euros.

# 9. 
# On a f(16)=3, on cherche x tel que f(16-x)=2 avec x une piece
# x = 1, 5 ou 10. Prenons x = 10, il reste 6 a rendre
# On a f(6)=2, on cherche x' tel que f(6-x')=1
# x' = 1 ou 5. Prenons x' = 5, il reste 1 a rendre
# On a f(1)=1, on cherche x'' tel que f(1-x'')=0
# x'' = 1
# On rends donc x, x', x'' = 10 + 5 + 1
# On peut choisir x = 5 ou 1 pour parcourir les autres branches

# 10. 
# Arbre de decisions a faire sur papier



## 4 - Reconstitution de solution

# 11. 
def rendu_memoise_reconstitue(systeme, somme):
	f = [0] * (somme + 1)
	g = [0] * (somme + 1)
	for s in range(1, somme + 1):
		f[s] = inf
		for x in systeme:
			if s >= x:
				if 1 + f[s - x] < f[s]:
					f[s] = 1 + f[s - x] # mise à jour du minimum
					g[s] = s - x        # on retient d'où l'on vient
	monnaie = []
	while somme > 0:
		monnaie.append(somme - g[somme])
		somme = g[somme]
	return monnaie

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