## TP14 -- Algorithmes gloutons



## Exercise 14.2 -- Rendu de monnaie : codage de l'algorithme glouton

## question 2) b)

# Voilà une première solution:
def renduMonnaie(somme, systeme):
	rendu = []
	restantDu = somme
	i = 0
	while restantDu > 0:
		valeur = systeme[i]
		if restantDu >= valeur:
			rendu.append(valeur)
			restantDu = restantDu - valeur
		else:
			i = i+1
	return rendu
	
# Voilà une deuxième solution:
def renduMonnaie1(somme, systeme):
	rendu = []
	restantDu = somme
	for valeur in systeme:
		while restantDu >= valeur:
			rendu.append(valeur)
			restantDu = restantDu - valeur
	return rendu

# Voilà une troisième solution:
def renduMonnaie2(somme, systeme):
	rendu = []
	restantDu = somme
	for valeur in systeme:
		nbValeur = restantDu//valeur
		restantDu = restantDu%valeur
		rendu = [valeur]*nbValeur + rendu
	return rendu

## question 3) b)

# Voici donc une solution récursive :
def renduMonnaie_rec(somme, systeme):
	if somme == 0:
		return []
	else:
		for valeur in systeme:
			if somme >= valeur:
				L = renduMonnaie_rec(somme - valeur, systeme)
				L.append(valeur)
				return L
				
# Voilà une deuxième façon d'écrire le même algorithme:
def renduMonnaie_rec1(somme, systeme):
	if somme == 0:
		return []
	else:
		for valeur in systeme:
			if somme >= valeur:
				return [valeur] + renduMonnaie_rec1(somme - valeur, systeme)




## Exercise 14.3 -- Le problème du sac à dos

## question 4) b)

def sacADosGlouton(listeNoms, listeMasses, listeValeurs, masseMaximale):
	n = len(listeNoms)
	donnees = []
	for i in range(n):
		nom = listeNoms[i]
		masse = listeMasses[i]
		valeur = listeValeurs[i]
		donnees.append( (valeur/masse, nom, masse) )
	
	donneesTriees = sorted(donnees, reverse = True)
	
	listeObjets = []
	masseRestante = masseMaximale
	for (_, nom, masse) in donneesTriees:
		if masse <= masseRestante:
			masseRestante = masseRestante - masse
			listeObjets.append(nom)
			
	return listeObjets



## Exercise 14.4 -- Allocations de salles

## question 1) a)

# On commence par coder une fonction auxiliaire qui teste
# si un cours est compatible avec un autre cours
def estCompatibleAvec(cours1, cours2):
	(h_debut_1, duree_1, _) = cours1
	(h_debut_2, duree_2, _) = cours2
	cas1 = h_debut_2 <= h_debut_1 < h_debut_2+duree_2
	cas2 = h_debut_2 < h_debut_1+duree_1 <= h_debut_2+duree_2
	if cas1 or cas2:
		return False
	else:
		return True
		
# On code une fonction qui teste si un cours est
# compatible avec une liste de cours donnés
def estCompatibleAvecListe(cours, listeCours):
	for c in listeCours:
		if not estCompatibleAvec(cours, c):
			return False
	return True

# Venons-en à la question
def coursChoisis(listeCours):
	L = []
	for c in listeCours:
		if estCompatibleAvecListe(c, L):
			L.append(c)
	return L

## question 2) a)

def coursChoisisEtCoursRestants(listeCours):
	coursChoisis = []
	coursRestants = []
	for c in listeCours:
		if estCompatibleAvecListe(c, coursChoisis):
			coursChoisis.append(c)
		else:
			coursRestants.append(c)
	return coursChoisis, coursRestants

## question 2) b)

# On va procéder récursivement :
def allocation(listeCours):
	if listeCours == []:
		return [], 0
	else:
		coursChoisis, coursRestants = coursChoisisEtCoursRestants(listeCours)
		listeListeCours, nbSalles = allocation(coursRestants)
		listeListeCours.append(coursChoisis)
		return listeListeCours, nbSalles+1



## Exercise 14.5 -- Stations d'essence

## question 1) c)

def glouton_iteratif(distances, dmax):
	L = []
	distanceAvantPanne = dmax
	i = 0
	for d in distances:
		if distanceAvantPanne >= d:
			distanceAvantPanne = distanceAvantPanne - d
-		else:
			L.append(i)
			distanceAvantPanne = dmax
-		i = i+1
	return L

## question c)

def choix_rec(distances, dmax, i, stations, d):
	n = len(distances)
	if i == n-1:
		return
	else:
		d_avant_station = distances[i]
		if d_avant_station >= d:
			choix_rec(distances, dmax, i+1, stations, d-d_avant_station)
		else:
			stations.append(i)
			choix_rec(distances, dmax, i+1, stations, dmax)