TD5 : Algorithmes gloutons, Programmation dynamique (problème du sac à dos)
TD 5
EX 1
1)
p = 5
k = 3
def glouton(somme):
global p
global k
for j in range(k,-1,-1):
if (somme - p**j>0):
g = glouton(somme - p**j)
g.append(p**j)
return g
else:
return [1]
print(glouton(17))
Par récurrence sur
- Pour
: c’est clair - Pour
: soit .
Montrons que
On pose
Donc
NB : En fait, les
sont les coefficients de la écrite en base , en moins de chiffres.
2) Dans le système
3)
Donnée : M
for i=2 to M do
min (
for j = 1 to k do
T[i-Pj]
)
T[i] <- T1
Programmation dynamique : Un moyen conceptuellement simple de trouver le nombre
de pièces permettant de rendre la valeur dans le système de pièces , est la programmation dynamique. En effet, supposons qu’on sache rendre de façon optimale toutes les valeurs strictement inférieure à . Pour rendre , il faut au moins une pièce, à prendre parmi possibles. Une fois choisie cette pièce, la somme restante inférieure strictement à , donc on sait la rendre de façon optimale. Il suffit donc d’essayer les possibilités :
Le nombre de calculs à effectuer est proportionnel à , donc exponentiel en la taille de .
BFS : Un Arbre enraciné peut être construit. Sa racine est la somme à rendre. Un nœud représente une somme intermédiaire. Les fils d’un nœud correspondent aux sommes restant à rendre selon la dernière pièce rendue (chaque pièce correspondant à une couleur d’arête attitrée).
La construction de l’arbre se fait en BFS, c’est-à-dire qu’on calcule les fils de tous les nœuds d’un niveau avant de passer au niveau suivant, et on s’arrête dès qu’un nœud 0 est trouvé : le chemin allant de la racine à ce nœud permet de rendre la monnaie avec un minimum de pièces.
EX 2
Algo naïf :
- on trie par ordre croissant
- si ils sont sur une droite en dimension
: on les trie par ordre lexicographique.
- si ils sont sur une droite en dimension
- on prend le segment
- on réitère avec le premier point hors du segment.
Il est optimal, car en notant
Comme tous les
EX 3
1)
Algo hyper naïf : on considère l’ensemble des parties convenables : les parties
Complexité: en
M2
⋯ | ⋯ | ⋯ |
⟶ le max.
T : tableau de taille W+1
∀i∈⟦0,n⟧, T[i]=0
Pour i=1 à W:
Pour k=1 à n:
Si (i-w_k)≥0:
T[i] ⟵ max(T[i], v_k + T[i-w_k])
Retourne T[W]
Invariant : pour tout
, est la récompense maixmale pour un sac à dos de taille .
Complexité : En posant
- en mémoire est en
- temporelle :
NB : on peut aussi ne mettre qu’une fois un élément, en retenant dans un array ceux qui ont déjà été mis.
Pq NP-complet ?: car la complexité est mesurée en fonction de la taille de l’entrée : i.e en unaire ⟹
est exponentiel par rapport à (nb de chiffres de l’entrée = taille de l’entrée).
2)
L’ensemble des parties convenable est
Complexité : comme on parcourt
M2
On trie les éléments par ordre décroissant de rapport qualité/prix, et on les place les uns après les autres : arrivé à la fin, on met une fraction adéquate de l’élément à placer.
T[n], S, j, P, b
for i=1 to n :
T[i] ⟵ (v_i/w_i, w_i)
trier(T)
i=1
while(i≤n and b)
if T[i][1]<W-P:
S ⟵ T[i][0] × T[i][1] + S
P ⟵ T[i][1] + P
i++
Sinon
S ⟵ S + (W-P)×T[i][0]
b ⟵ false
Leave a comment