Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# Solveur de Sac à Dos par Branch and Bound
Programme Java implémentant l'algorithme Branch and Bound avec relaxation fractionnaire pour résoudre le problème du sac à dos 0/1 de manière optimale.
## Fonctionnalités
- Algorithme d'exploration avec élagage par bornes
- Calcul de borne supérieure par méthode fractionnaire
- Lecture des données depuis un fichier texte
- Tri préalable des objets par ratio valeur/poids
- Statistiques d'exécution (nœuds explorés)
- Affichage de la solution optimale détaillée
## Prérequis
- Java JDK 11 ou supérieur
- Fichier d'instance au format spécifié
## Installation
1. Cloner/déposer les fichiers sources dans un dossier
2. Modifier le chemin du fichier dans `App.java` :
```java
// Ligne à modifier dans App.java
Backpack backpack = new InstanceReader().read("chemin/vers/votre_fichier.txt");
```
## Compiler le projet :
```bash
javac -d bin src/*.java
```
## Utilisation
```bash
java -cp bin App
```
## Exemple de sortie :
La valeur optimale est : 220
Objets inclus dans la solution optimale : [true, false, true, true]
Nombre de nœuds explorés : 27
## Structure du code
| Classe | Description |
|-----------------|----------------------------------------------|
| Backpack | Implémente l'algorithme principal |
| Loot | Représente un objet avec ratio valeur/poids |
| InstanceReader | Lit et parse les fichiers d'instance |
| App | Point d'entrée du programme |
## Membre(s) du projet
- OUATTARA Sie
- GOUNOU Boubacar
## Licence
MIT License - Libre d'utilisation et modification