Morsli Omar

Belarbi Elouanes

Bourouba Mohamed Anis

TP – Mini-projet NP-Complétude
Partie I. Théorique :
Question 1 : Présentation du problème du sac à dos
Exemple introductif :

Imaginez qu’un voleur pénètre dans une maison et trouve une liste
d’objets précieux à voler. Chaque objet a une certaine valeur et un certain
poids. Cependant, son sac a une capacité maximale (un poids qu’il ne
peut pas dépasser). Son objectif est de maximiser la valeur totale des
objets volés tout en respectant la limite de poids de son sac.

Par exemple :

Il y a trois objets dans la maison :

Un vase antique de valeur 10 pesant 5 kg.

Une télévision de valeur 40 pesant 20 kg.

Un ordinateur portable de valeur 30 pesant 10 kg.

Le sac du voleur peut transporter jusqu’à 30 kg.

Quelle combinaison d’objets permet de maximiser la valeur totale qu’il

peut voler sans dépasser la capacité du sac ?

Définition générale (non formelle) :

Le problème du sac à dos consiste à choisir des objets dans une liste,
chacun ayant une valeur et un poids, de manière à maximiser la valeur
totale des objets sélectionnés tout en respectant une contrainte sur le
poids total.
Applications pratiques :

Ce problème se retrouve dans de nombreux domaines :

Optimisation de ressources : Allouer des ressources limitées à différents

projets.

Logistique : Charger des camions ou conteneurs de manière optimale.

Sécurité informatique : Résoudre certains problèmes en cryptographie.

Question 2 : Définition Formelle :

Une définition formelle du problème du sac à dos est donnée comme suit :

Instance :
- Une liste d'objets, où chaque objet i possède :
- Un poids wᵢ,
- Une valeur vᵢ.
- Une capacité maximale W pour le sac.
Formulé comme :
Instance = {(w₁, v₁), (w₂, v₂), ..., (wₙ, vₙ)}, W

Peut-on choisir un sous-ensemble d'objets S ⊆ {1, 2, ..., n} tel que :

Question :

Σ wᵢ ≤ W (pour i ∈ S),
- Le poids total des objets sélectionnés ne dépasse pas la capacité W :

Σ vᵢ est maximale (pour i ∈ S).

- Et la valeur totale des objets sélectionnés est maximale :

Remarque :
Si la question est posée en termes de décision, on peut demander si un
sous-ensemble S existe pour atteindre une valeur cible V tout en

Σ wᵢ ≤ W et Σ vᵢ ≥ V (pour i ∈ S).
respectant la capacité :
Question 3 : Structure de données pour représenter une
instance :
Une instance du problème du sac à dos est composée de deux éléments :

1) Un ensemble d'objets, chaque objet ayant une valeur et un poids.

2) Une capacité maximale, qui représente la contrainte du sac.

Une structure de données pour représenter une instance peut être définie
comme suit :

-Une liste ou un tableau pour représenter les objets. Chaque objet est un
couple (Vi,Pi), où Vi est la valeur et Pi le poids.

-Une variable pour représenter la capacité maximale.

Exemple de représentation (en Python) :

#Classe pour représenter un objet du sac à dos.

class Objet:

def __init__(self, valeur, poids):

[Link] = valeur #param valeur: Valeur de l'objet

[Link] = poids #param poids: Poids de l'objet

#Classe pour représenter une instance du problème du sac à dos.

class Instance:

def __init__(self, objets, capacite):

[Link] = objets # Liste d'objets de type Objet

[Link] = capacite # Capacité maximale du sac

Example :

# Créer des objets

objet1 = Objet(10, 5)

objet2 = Objet(40, 20)

objet3 = Objet(30, 10)

# Créer une liste d'objets et une instance du sac à dos

objets = [objet1, objet2, objet3]

capacite = 30

instance = Instance(objets, capacite)

Question 4 : Structure de données pour représenter une

solution :
Une solution au problème du sac à dos est un sous-ensemble d'objets
sélectionnés. Elle peut être représentée par :

1) Une liste binaire, où chaque position indique si un objet est sélectionné

(1) ou non (0).

2) Valeur totale : La somme des valeurs des objets inclus.

3) Poids total : La somme des poids des objets inclus.

4) Un attribut pour vérifier si la solution est valide.

Exemple de représentation (En Python) :

#Classe pour représenter une solution détaillée au problème du sac à dos.

class Solution:

def __init__(self, selection, valeur_totale=0, poids_total=0,

valide=False):

[Link] = selection #Liste binaire (1 pour inclus, 0 pour exclu)

self.valeur_totale = valeur_totale

self.poids_total = poids_total

[Link] = valide

Example :

Pour une instance avec 3 objets et une capacité de 30 :

Solution : Inclure les objets 1 et 3, exclure l'objet 2.

Valeur totale : 10+30=40.

 Poids total : 5+10=15.

Solution valide : Oui.

solution = Solution([1, 0, 1], valeur_totale=40, poids_total=15,

valide=True)

Question 5 : Exemple d'Instance et Résultats :

Voici une instance exemple pour le problème du sac à dos :

Objets :
- Objet 1 : (w₁ = 2, v₁ = 3),
- Objet 2 : (w₂ = 3, v₂ = 4),
- Objet 3 : (w₃ = 4, v₃ = 5),
- Objet 4 : (w₄ = 5, v₄ = 6).
Capacité du sac : W = 8.

# Exemples Respectant la Contrainte :

1. Sous-ensemble S = {Objet 1, Objet 3} :

- Poids total : 2 + 4 = 6,
- Valeur totale : 3 + 5 = 8,
- Respecte la contrainte : Oui.

2. Sous-ensemble S = {Objet 2, Objet 4} :

- Poids total : 3 + 5 = 8,
- Valeur totale : 4 + 6 = 10 (solution optimale),
- Respecte la contrainte : Oui.

3. Sous-ensemble S = {Objet 1, Objet 4} :

- Poids total : 2 + 5 = 7,
- Valeur totale : 3 + 6 = 9,
- Respecte la contrainte : Oui.

# Exemples Ne Respectant Pas la Contrainte :

1. Sous-ensemble S = {Objet 1, Objet 2, Objet 3} :

- Poids total : 2 + 3 + 4 = 9,
- Valeur totale : 3 + 4 + 5 = 12,
- Respecte la contrainte : Non (poids dépasse la capacité W = 8).
2. Sous-ensemble S = {Objet 3, Objet 4} :
- Poids total : 4 + 5 = 9,
- Valeur totale : 5 + 6 = 11,
- Respecte la contrainte : Non (poids dépasse la capacité W = 8)

Question 6 : Algorithme de résolution aveugle :

algorithme de recherche en profondeur :

Fonction DFS(index, poids_actuel, valeur_actuelle) :

Si poids_actuel dépasse la capacité :

Retourner 0 // Solution invalide

Si index est hors limites (tous les objets ont été examinés) :

Retourner valeur_actuelle // Fin de la branche

// Explorer la solution sans cet objet

valeur_sans_objet = DFS(index + 1, poids_actuel, valeur_actuelle)

// Explorer la solution avec cet objet

valeur_avec_objet = DFS(index + 1,

poids_actuel + poids[index],

valeur_actuelle + valeur[index])

// Retourner la meilleure solution entre les deux options

Retourner max(valeur_sans_objet, valeur_avec_objet)

// Appel initial

DFS(0, 0, 0)

algorithme de recherche en largeur:

Fonction BFS(objets, capacité) :

Créer une file pour stocker les états possibles

 Ajouter l'état initial (index = 0, poids = 0, valeur = 0)

max_valeur = 0 // meilleure valeur trouvée

Tant que la file n'est pas vide :

Extraire un état (index, poids_actuel, valeur_actuel)

Si poids_actuel dépasse la capacité :

Continuer // Ignorer cet état

Si valeur_actuel > max_valeur :

max_valeur = valeur_actuel

Si index est encore valide :

Ajouter (index + 1, poids_actuel, valeur_actuel)

// Ajouter l'état où l'objet courant est pris

Ajouter (index + 1,

poids_actuel + poids[index],

valeur_actuel + valeur[index])

Retourner max_valeur

Question 7 : Ecrire une fonction ou algorithme de vérification

d’une solution et calculer sa complexité :
A)

Une fonction de vérification doit :

1) Vérifier la validité d'une solution :

Le poids total des objets sélectionnés ne doit pas dépasser la

capacité maximale C.
2) Retourner les résultats :

Un indicateur de validité.

La valeur totale et le poids total associés à la solution pour la

crédibilité.

Algorithme :

1) Initialiser les variables poids_total et valeur_totale à 0.

2) Parcourir les objets et leur état dans la solution binaire :

Si l'objet est sélectionné (valeur de la solution binaire = 1), ajouter

son poids et sa valeur.

3) Comparer le poids_total à la capacité maximale C.

4) Retourner le résultat.

def verifier(objets, capacite, solution):

poids_total = 0

valeur_totale = 0

# Vérification de la validité de la solution binaire

if len(solution) != len(objets):

return False, 0, 0 # Longueur de la solution invalide

# Calcul des poids et valeurs totaux

for i, choisi in enumerate(solution):

if choisi == 1: # Si l'objet est inclus

poids_total += objets[i][1]

valeur_totale += objets[i][0]

# Vérification que le poids total respecte la capacité

if poids_total > capacite:

return False, valeur_totale, poids_total

 return True, valeur_totale, poids_total

Example :

objets = [(10, 5), (40, 20), (30, 10)]

capacite = 30

solution = [1, 0, 1]

valid, valeur_totale, poids_total = verifier_solution(objets, capacite,

solution)

print(f"Validité : {valid}")

print(f"Valeur totale : {valeur_totale}")

print(f"Poids total : {poids_total}")

Résultat attendue :

Valid : True

Valeur totale : 40

Poids total : 15

B) Complexité :

ligne 1 : 1

ligne 2 : 1

ligne 3 : 1

ligne 4 : n

ligne 5 : 2n

ligne 6 : 2n

ligne 7 : 1

ligne 8 : 1

1+1+1+n+2n+2n+1+1 = O(n)
Question 8 : Conclusion
Le problème du sac à dos est difficile à résoudre quand il y a beaucoup
d’objets, car il faut essayer toutes les combinaisons possibles pour trouver
la meilleure solution. Cela prend beaucoup de temps.

Dans la vie réelle, il est utile pour organiser des ressources limitées,
comme optimiser un espace ou gérer un budget. Les méthodes exactes
donnent la meilleure solution mais sont lentes, tandis que les méthodes
approximatives trouvent des solutions rapides mais pas toujours parfaites.

#Conclusion :
C’est un problème important qui montre qu’il faut parfois faire des
compromis entre trouver la solution parfaite et gagner du temps.