TP 2 : Problème du sac à dos#

On rappelle le problème du sac à dos :

Entrée : une capacité \(c\) et des objets de poids \(w_1, ..., w_n\) et valeurs \(v_1\), …, \(v_n\).
Sortie : la valeur maximum que l’on peut mettre dans un sac de capacité \(c\).

\(c\) est le poids total maximum que l’on peut peut mettre dans le sac

L’objectif du TP est de comparer l’algorithme de programmation dynamique vu en cours à des algorithmes gloutons.

Algorithmes gloutons#

Un algorithme glouton consiste à ajouter des objets un par un au sac, en choisissant à chaque étape l’objet qui a l’air le plus intéressant, si son poids n’excède pas la capacité restante du sac.
Suivant l’ordre dans lequel on choisit les objets, on obtient des algorithmes gloutons différents.

Question

Écrire une fonction glouton(c, w, v) qui renvoie la valeur totale des objets choisis par l’algorithme glouton, en considérant les objets dans l’ordre donné par w et v (on regarde d’abord l’objet de poids w[0] et valeur v[0], puis l’objet de poids w[1] et valeur v[1]…).
Tester avec l’exemple ci-dessous. Le résultat est-il optimal ?

Solution

def glouton(c, w, v):
    """Renvoie la valeur maximum qu'on peut obtenir avec les objets
    c: capacité du sac
    w: poids des objets
    v: valeur des objets
    """
    poids = 0
    valeur = 0
    for i in range(len(w)):
        if poids + w[i] <= c:
            poids += w[i]
            valeur += v[i]
    return valeur

glouton(10, [5, 3, 6], [4, 4, 6])

Tri des objets#

Question

Écrire une fonction combine(L1, L2) qui renvoie la liste des couples (L1[i], L2[i]). On suppose que L1 et L2 ont la même longueur.

Solution

def combine(L1, L2):
    L = []
    for i in range(len(L1)):
        L.append((L1[i], L2[i]))
    return L

combine([1, 2, 3], [4, 5, 6])

[(1, 4), (2, 5), (3, 6)]

Question

Écrire une fonction split(L) telle que si L est une liste de couples, split(L) renvoie deux listes L1 et L2 où L1 contient les premiers éléments des couples de L et L2 les seconds éléments des couples de L.

Solution

def split(L):
    L1 = []
    L2 = []
    for i in range(len(L)):
        L1.append(L[i][0])
        L2.append(L[i][1])
    return L1, L2

split([(1, 4), (2, 5), (3, 6)])

([1, 2, 3], [4, 5, 6])

Si L est une liste, L.sort() trie L par ordre croissant (L.sort(reverse=True) pour trier par ordre décroissant). Si L contient des couples, la liste est triée suivant le premier élément de chaque couple (ordre lexicographique).
Exemple :

L = [(1, 4), (7, 5), (3, 6)]
L.sort()
L # trié suivant le 1er élément de chaque couple

[(1, 4), (3, 6), (7, 5)]

Question

Écrire une fonction tri_poids(w, v) qui renvoie les listes w2 et v2 obtenues à partir de w et v en triant les poids par ordre croissant. On pourra utiliser L.sort, combine et split.

Solution

def tri_poids(w, v):
    L = combine(w, v)
    L.sort()
    return split(L)

tri_poids([5, 3, 6], [42, 0, 2])

([3, 5, 6], [0, 42, 2])

Stratégies gloutonnes#

Question

En déduire une fonction glouton_poids(c, w, v) qui renvoie la valeur totale des objets choisis par l’algorithme glouton, en considérant les objets dans l’ordre de poids croissant. On pourra réutiliser glouton.
Est-ce que cet algorithme est toujours optimal ?

Solution

def glouton_poids(c, w, v):
    w, v = tri_poids(w, v)
    return glouton(c, w, v)

glouton_poids(10, [5, 3, 6], [4, 4, 10])

Question

Écrire de même des fonctions tri_valeur(w, v) et glouton_valeur(c, w, v) qui renvoie la valeur totale des objets choisis par l’algorithme glouton, en considérant les objets dans l’ordre de valeur décroissante (en utilisant L.sort(reverse=True)). Est-ce que cet algorithme est toujours optimal ?

Solution

def tri_valeur(w, v):
    L = combine(v, w)
    L.sort(reverse=True)
    L1, L2 = split(L)
    return L2, L1

def glouton_valeur(c, w, v):
    w, v = tri_valeur(w, v)
    return glouton(c, w, v)

glouton_valeur(10, [5, 4, 7], [4, 4, 6])

Question

De même, écrire une fonction glouton_ratio(c, w, v) qui renvoie la valeur totale des objets choisis par l’algorithme glouton, en considérant les objets dans l’ordre de ratio valeur/poids décroissant. On pourra utiliser deux fois combine.

Solution

def tri_ratio(v, w):
    L = combine(v, w)
    L = combine([v[i]/w[i] for i in range(len(v))], L)

    L.sort(reverse=True)
    return split(split(L)[1])

def glouton_ratio(c, w, v):
    v, w = tri_ratio(v, w)
    return glouton(c, w, v)

glouton_ratio(10, [5, 4, 7], [4, 4, 6])

Programmation dynamique#

On rappelle le problème du sac à dos :

Entrée : une capacité \(c\) et des objets de poids \(w_1, ..., w_n\) et valeurs \(v_1\), …, \(v_n\).
Sortie : la valeur maximum que l’on peut mettre dans un sac de capacité \(c\).

Soit \(dp[i][j]\) la valeur maximum que l’on peut mettre dans un sac de capacité \(i\), en ne considérant que les \(j\) premiers objets. On suppose que les poids sont strictement positifs.

Question

Que vaut \(dp[i][0]\) ?

Solution

\(dp[i][0] = 0\) : on ne peut pas mettre d’objet dans un sac de capacité \(0\).

Question

Exprimer \(dp[i][j]\) en fonction de \(dp[i][j-1]\) dans le cas où \(w_j > i\).

Solution

\(dp[i][j] = dp[i][j-1]\) : on ne peut pas mettre l’objet \(j\) dans le sac de capacité \(i\).

Question

Supposons \(w_j \leq i\). Donner une formule de récurrence sur \(dp[i][j]\), en distinguant le cas où l’objet \(j\) est choisi et le cas où il ne l’est pas.

Solution

\[dp[i][j] = \max(\underbrace{dp[i][j - 1]}_{\text{sans prendre } o_j}, \underbrace{dp[i - w_j][j - 1] + v_j}_{\substack{\text{en prenant } o_j}, \text{si }i - w_j \geq 0})\]

Question

En déduire une fonction prog_dyn(c, w, v) qui renvoie la valeur maximum que l’on peut mettre dans un sac de capacité \(c\), en ne considérant que les \(j\) premiers objets, en remplissant une matrice dp de taille \((c+1) \times (n+1)\).

Solution

def prog_dyn(c, w, v):
    n = len(w)
    dp = [[0 for j in range(c+1)] for i in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, c+1):
            if j < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
    return dp[n][c]

prog_dyn(10, [5, 4, 7], [4, 4, 6])

Comparaison#

Question

Écrire une fonction genere_instance() qui renvoie un triplet \((c, w, v)\), où \(c\) est un entier aléatoire entre 1 et 1000 et \(w\), \(v\) sont des listes de 100 entiers aléatoires entre 1 et 100.
On importera random pour utiliser random.randint(a, b) qui génère un entier aléatoire entre \(a\) et \(b\) inclus.

Solution

import random

def genere_instance():
    c = random.randint(1, 1000)
    w = [random.randint(1, 100) for i in range(100)]
    v = [random.randint(1, 100) for i in range(100)]
    return c, w, v

Question

Afficher, pour chaque stratégie gloutonne (ordre de poids, ordre de valeur, ordre de ratio), l’erreur commise par rapport à la solution optimale, en moyennant sur 100 instances générées par genere_instance().
Quelle stratégie gloutonne est la plus efficace ?

Solution

gp, gv, gr = 0, 0, 0
for i in range(100):
    c, w, v = genere_instance()
    sol = prog_dyn(c, w, v)
    gp += glouton_poids(c, w, v)/sol
    gv += glouton_valeur(c, w, v)/sol
    gr += glouton_ratio(c, w, v)/sol
print(f"Glouton poids : {gp/100}")
print(f"Glouton valeur : {gv/100}")
print(f"Glouton ratio : {gr/100}")

Question

Comparer le temps total d’exécution de la stratégie gloutonne par ratio et de la programmation dynamique, sur 100 instances générées par genere_instance(). On pourra importer time et utiliser time.time() pour obtenir le temps actuel en secondes.

Solution

import time

t1, t2 = 0, 0
for i in range(100):
    c, w, v = genere_instance()
    t = time.time()
    glouton_poids(c, w, v)
    t1 += time.time() - t
    t = time.time()
    prog_dyn(c, w, v)
    t2 += time.time() - t
print(f"Glouton poids : {t1} s")
print(f"Programmation dynamique : {t2} s")

Obtenir la liste des objets choisis#

Question

Réécrire la fonction prog_dyn(c, w, v) pour qu’elle renvoie la liste des objets choisis. Pour cela, on peut construire la matrice dp et remarquer que :

si \(dp[i][j] = dp[i][j-1]\), alors l’objet \(j\) n’est pas choisi ;
si \(dp[i][j] = dp[i - w_j][j - 1] + v_j\), alors l’objet \(j\) est choisi.
On peut donc construire la liste des objets choisis en remontant la matrice dp à partir de la case \((c, n)\).

Solution

def prog_dyn(c, w, v):
    n = len(w)
    dp = [[0 for j in range(c+1)] for i in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, c+1):
            if j < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])

    # reconstruction de la solution
    i, j = n, c
    sol = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            sol.append(i-1)
            j -= w[i-1]
            i -= 1
    return sol

prog_dyn(10, [5, 4, 7], [4, 4, 6]) 
# la solution optimale consiste à choisir les objets 1 et 0

[1, 0]

Informatique commune en 2ème année de CPGE

TP 2 : Problème du sac à dos

Contents

TP 2 : Problème du sac à dos#

Algorithmes gloutons#

Tri des objets#

Stratégies gloutonnes#

Programmation dynamique#

Comparaison#

Obtenir la liste des objets choisis#