Rédaction d'algorithmes dynamiques

6.1 Principales étapes dans le développement d'algorithmes dynamiques.

Principales étapes dans le développement d'algorithmes dynamiques

1. Définition des sous-problèmes :

Décompose le problème en sous-problèmes plus petits, qui peuvent être résolus indépendamment les uns des autres. Ces sous-problèmes doivent se chevaucher, afin que tu puisses utiliser les résultats des calculs précédents.

2. Identification des états :

Définis tous les états possibles qui peuvent survenir lors de la résolution du problème. Les états doivent décrire toutes les informations nécessaires pour passer d'une étape à la suivante.

3. Formulation de la relation de récurrence :

Détermine comment la solution du problème pour l'état actuel dépend des solutions pour les états précédents. Cette relation doit exprimer comment obtenir la solution optimale en utilisant les solutions pour les sous-problèmes.

4. Définition des cas de base :

Définis les cas de base pour lesquels la solution du problème est connue directement, sans nécessiter de calculs supplémentaires.

5. Remplissage du tableau :

Crée un tableau (généralement un tableau ou une matrice) pour stocker les solutions de tous les sous-problèmes. Utilise la relation de récurrence et les cas de base pour remplir le tableau de bas en haut ou de haut en bas.

6. Optimisation (mémorisation) :

Si une approche récursive est utilisée, ajoute de la mémorisation pour enregistrer les résultats des sous-problèmes et éviter leurs recalculs.

Complexité temporelle et spatiale des algorithmes dynamiques

Complexité temporelle :

• La complexité temporelle des algorithmes dynamiques est généralement exprimée en fonction du nombre de sous-problèmes et du temps nécessaire pour calculer chaque sous-problème.
• Dans la plupart des cas, la complexité temporelle est de O(n) ou O(n^2), où n est la taille des données d'entrée.

Complexité spatiale :

• La complexité spatiale dépend du nombre d'états à stocker.
• Dans certains cas, il est possible de réduire la complexité spatiale en utilisant des optimisations telles que la réduction de la mémoire utilisée jusqu'à O(n) ou O(1).

6.2 Le problème du sac à dos.

Le problème du sac à dos est un problème classique d'optimisation combinatoire, qui se pose dans divers domaines, y compris l'informatique, l'économie et la gestion logistique. L'objectif principal du problème est d'utiliser les ressources limitées de la manière la plus efficace possible.

Description du problème du sac à dos

On a un sac à dos qui peut supporter un certain poids W. On a aussi n objets, chacun ayant un poids wt[i] et une valeur val[i] spécifiques. Il faut déterminer quels objets prendre pour maximiser la valeur totale des objets dans le sac à dos, sans dépasser sa capacité en poids.

Types de problèmes de sac à dos

1. Problème du sac à dos 0/1 (0/1 Knapsack Problem):

Chaque objet peut être soit pris, soit non pris (on ne peut pas le prendre partiellement).

2. Problème du sac à dos fractionnaire (Fractional Knapsack Problem):

Chaque objet peut être divisé et n'importe quelle partie peut être prise.

3. Problème du sac à dos multiple (Multiple Knapsack Problem):

Il y a plusieurs sacs à dos avec différentes limitations de poids.

Formulation du problème du sac à dos 0/1 en termes de théorie des algorithmes:

Relation de récurrence :

Pour chaque objet i et pour chaque poids possible w (de 0 à W), la solution optimale peut s'exprimer comme suit :

• Si l'objet i n'est pas inclus dans le sac à dos, la valeur optimale est la valeur optimale pour les i − 1 objets et le poids w.
• Si l'objet i est inclus dans le sac à dos, la valeur optimale est la valeur de cet objet plus la valeur optimale pour les i − 1 objets et le poids w − wt[i].

Complexité temporelle et spatiale

Complexité temporelle :

La complexité temporelle de cet algorithme est O(nW) où n est le nombre d'objets et W est la capacité du sac à dos. Cela est dû au fait qu'il faut remplir un tableau de taille n × W.

Complexité spatiale :

La complexité spatiale est également O(nW), car il est nécessaire d'avoir un tableau pour stocker les résultats intermédiaires.

Exemples de mise en œuvre du problème du sac à dos 0/1

def knapsack(W, wt, val, n):
    # Création du tableau pour stocker les valeurs intermédiaires
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
        
    # Remplissage du tableau dp de bas en haut
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
        
    return dp[n][W]
        
# Exemple d'utilisation
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(f"Valeur maximale du sac à dos : {knapsack(W, wt, val, n)}")
        

6.3 Problème du rendu de monnaie.

Le problème du rendu de monnaie est un problème classique de programmation dynamique, qui consiste à trouver le nombre minimal de pièces ou le nombre de façons de constituer une somme d'argent donnée à partir d'un ensemble de pièces avec des valeurs nominales données. Ce problème a deux variantes principales :

Nombre minimal de pièces (Minimum Coin Change Problem):

Trouver le nombre minimal de pièces qui totalisent une somme donnée.

Nombre de façons (Number of Ways to Make Change):

Trouver le nombre de façons différentes de constituer une somme donnée à partir de l'ensemble donné de pièces.

Option 1. Nombre minimal de pièces

Énoncé du problème

Données :

• Nombre illimité de pièces avec des valeurs nominales spécifiques.
• Montant cible S.

Il faut :

• Trouver le nombre minimal de pièces qui permet de constituer la somme S.

Solution utilisant la programmation dynamique

Relation de récurrence :

• Soit dp[i] le nombre minimal de pièces nécessaire pour constituer la somme i.
• Pour chaque pièce c de l'ensemble des pièces, si i ≥ c, alors : dp[i] = min(dp[i], dp[i − c] + 1)

Cas de base :

• dp[0] = 0 (pour la somme 0, il faut 0 pièces).

Complexité temporelle et spatiale :

• Complexité temporelle : O(n ⋅ S), où n est le nombre de valeurs nominales des pièces, S est le montant cible.
• Complexité spatiale : O(S), car un tableau est nécessaire pour stocker le nombre minimal de pièces pour chaque somme de 0 à S.

Exemple de réalisation en Python

def min_coins(coins, S):
    dp = [float('inf')] * (S + 1)
    dp[0] = 0
        
    for i in range(1, S + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
    return dp[S] if dp[S] != float('inf') else -1
        
# Exemple d'utilisation
coins = [1, 2, 5]
S = 11
print(f"Nombre minimal de pièces pour la somme {S} : {min_coins(coins, S)}")
        
        

Le problème du rendu de monnaie illustre la flexibilité de la programmation dynamique. Il est utilisé pour enseigner et explorer les techniques algorithmiques, car il montre comment les relations de récurrence et les cas de base peuvent être utilisés pour résoudre efficacement les problèmes.