TP 2 - Knapsack

TP 2 - Knapsack#

Pour programmer, vous pouvez soit utiliser Pyzo, soit Basthon.

Commandes Basthon :

  • Ctrl + Entrée : exécuter la cellule

  • Shift + Entrée : exécuter la cellule puis passer à la suivante

  • Entrée : passer en mode édition

  • Échap : sortir du mode édition

Les commandes suivantes sont valables uniquement hors du mode édition :

  • A : créer une nouvelle cellule (en haut)

  • B : créer une nouvelle cellule (en bas)

  • D D : supprimer la cellule

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

Hide code cell content 
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])

8

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

Hide code cell content 
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

Hide code cell content 
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

Hide code cell content 
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

Hide code cell content 
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])

8

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

Hide code cell content 
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])

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

Hide code cell content 
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])

8

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 quand on a pas d’objets…

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

Hide code cell content 
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])

8

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

Hide code cell content 
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

Hide code cell content 
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}")

Glouton poids : 0.839421529494039
Glouton valeur : 0.6275781393288896
Glouton ratio : 0.9913779471066019

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

Hide code cell content 
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")

Glouton poids : 0.0025434494018554688 s
Programmation dynamique : 0.9669291973114014 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

Hide code cell content 
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]

Plus long chemin croissant dans une matrice#

Etant donnée une matrice d’entiers de taille m x n, quelle est la longueur du plus long chemin croissant dans cette matrice ?

Pour chaque élément dans la matrice, on peut bouger dans les quatre directions (haut, bas, droite et gauche) mais pas en diagonale ou en dehors de la matrice.

Exemple 1 :

Exemple 2 :

Question

Proposez une fonction renvoyant la longueur du plus long chemin croissant dans une matrice. Votre solution devra utiliser de la programmation dynamique.

Indice 1

Posez les cas limites qui vont vous embeter et pensez à votre structure de données.

Indice 2

Utilisez une fonction auxiliaire qui vous résoud un sous-problème…

Indice 3

… c’est à dire une fonction qui résoud le plus grand chemin croissant en partant d’une cellule donnée dans la matrice.

Solution

Vous êtes vraiment sur de vouloir abandonner si proche du but ?

Hide code cell content 
m1 = [[9,9,4],[6,6,8],[2,1,1]]
m2 = [[3,4,5],[3,2,6],[2,2,1]]


def lip(mat, i, j, d):
    current = mat[i][j]
    bn = [0,0,0,0] #better neighbours
    left = right = top = bottom = True

    if i <= 0:
        top = False
    if i >= len(mat)-1:
        bottom = False
    if j <= 0:
        left = False
    if j >= len(mat[0])-1:
        right = False

    if top:
        if mat[i-1][j]>current:
            if d[i-1][j] == 0:
                d[i-1][j] = lip(mat,i-1,j, d)
            bn[0] = d[i-1][j]
    if bottom:
        if mat[i+1][j]>current:
            if d[i+1][j] == 0:
                d[i+1][j] = lip(mat,i+1,j, d)
            bn[1] = d[i+1][j]
    if left:
        if mat[i][j-1]>current:
            if d[i][j-1] == 0:
                d[i][j-1] = lip(mat,i,j-1, d)
            bn[2] = d[i][j-1]
    if right:
        if mat[i][j+1]>current:
            if d[i][j+1] == 0:
                d[i][j+1] = lip(mat,i,j+1, d)
            bn[3] = d[i][j+1]

    if d[i][j] == 0:
        d[i][j] = 1 + max(bn[0] ,bn[1], bn[2], bn[3])
    return 1 + max(bn[0] ,bn[1], bn[2], bn[3])

def longestIncreasingPath(mat):
    d = [[0]*len(mat[0]) for _ in range(len(mat))]
    max_coords=(0,0)
    maxi = 0
    for i in range(len(mat)):
        for j in range(len(mat[0])):
            if lip(mat, i, j, d) > maxi:
                max_coords = (i,j)
                maxi = lip(mat, i, j, d)
    return maxi, max_coords, d

longestIncreasingPath(m1)

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

longestIncreasingPath(m2)

(4, (0, 0), [[4, 3, 2], [1, 4, 1], [2, 1, 2]])
Contents