Programmation dynamique

def knapsack(c, w, v):
    """ 
    Renvoie la valeur maximum que l'on peut mettre
    dans un sac à dos de capacité c.
    Le ième objet a pour poids w[i] et valeur v[i].
    """
    n = len(w) # nombre d'objets
    dp = [[0]*(n + 1) for i in range(c + 1)]
    # dp[i][j] = valeur max dans un sac de capacité i
    # où j est le nombre d'objets autorisés
    for i in range(1, c + 1):
        for j in range(1, n + 1):
            if w[j - 1] <= i:
                x = v[j - 1] + dp[i - w[j - 1]][j - 1]
                dp[i][j] = max(dp[i][j - 1], x)
            else:
                dp[i][j] = dp[i][j - 1]
    return dp[c][n]

w = [2, 2, 2, 3, 5, 6, 8]
v = [1, 1, 1, 7, 10, 10, 18]
knapsack(10, w, v)

19

def knapsack2(c, w, v):
    n = len(w)
    dp = [0]*(c + 1)
    for j in range(n):
        dp_ = dp[:] # copie de dp
        for i in range(c + 1):
            if w[j] <= i:
                dp[i] = max(dp_[i], v[j] + dp_[i - w[j]])
    return dp[-1]

knapsack2(10, w, v)

19

def knapsack_memo(c, w, v):
    dp = {}
    def aux(i, j):
        if i == 0 or j == 0:
            return 0
        if (i, j) not in dp:
            dp[(i, j)] = aux(i, j - 1)
            if w[j - 1] <= i:
                dp[(i, j)] = max(dp[(i, j)], v[j - 1] + aux(i - w[j - 1], j - 1))
        return dp[(i, j)]
    return aux(c, len(w))

knapsack_memo(10, w, v)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In [2], line 13
     10         return dp[(i, j)]
     11     return aux(c, len(w))
---> 13 knapsack_memo(10, w, v)

NameError: name 'w' is not defined

from functools import cache

def knapsack_memo2(c, w, v):
    @cache
    def aux(i, j):
        if i == 0 or j == 0:
            return 0
        v = aux(i, j - 1)
        if w[j - 1] <= i:
            v = max(v, v[j - 1] + aux(i - w[j - 1], j - 1))
        return v
    return aux(c, len(w))

knapsack_memo2(10, w, v)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In [1], line 14
     11         return v
     12     return aux(c, len(w))
---> 14 knapsack_memo2(10, w, v)

NameError: name 'w' is not defined

Plus courts chemins

\[\begin{split}M = \begin{pmatrix} 0 & 3 & 8 & \infty & -4\\ \infty & 0 & \infty & 1 & 7\\ \infty & 4 & 0 & \infty & \infty\\ 2 & \infty & -5 & 0 & \infty\\ \infty & \infty & \infty & 6 & 0\\ \end{pmatrix} \end{split}\]

g = [
    [0, 3, 8, float("inf"), -4],
    [float("inf"), 0, float("inf"), 1, 7],
    [float("inf"), 4, 0, float("inf"), float("inf")],
    [2, float("inf"), -5, 0, float("inf")],
    [float("inf"), float("inf"), float("inf"), 6, 0]
]

g

[[0, 3, 8, inf, -4],
 [inf, 0, inf, 1, 7],
 [inf, 4, 0, inf, inf],
 [2, inf, -5, 0, inf],
 [inf, inf, inf, 6, 0]]

Bellman-Ford

def bellman(g, r):
    n = len(g)
    dist = [float("inf") for i in range(n)]
    dist[r] = 0
    for k in range(n - 2):
        for u in range(n):
            for v in range(len(g[u])):
                if g[u][v] != 0:
                    dist[v] = min(dist[v], dist[u] + g[u][v])
    return dist

bellman(g, 0)

[0, 1, -3, 2, -4]

Floyd-Warshall

import copy

def floydwarshall(g):
    n = len(g)
    dist = copy.deepcopy(g)
    for k in range(n):
        for u in range(n):
            for v in range(n):
                dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v])
    return dist

floydwarshall(g)

[[0, 1, -3, 2, -4],
 [3, 0, -4, 1, -1],
 [7, 4, 0, 5, 3],
 [2, -1, -5, 0, -2],
 [8, 5, 1, 6, 0]]