Ce projet propose deux algorithmes pour résoudre un problème d'optimisation d'investissement, où l'objectif est de maximiser le profit obtenu à partir d'un budget fixe. Les deux solutions sont implémentées en Python et présentent des approches contrastées : une méthode par force brute et une méthode gloutonne.
bruteforce.py: Implémentation de l'algorithme par force brute.optimized.py: Implémentation de l'algorithme glouton.actions_list.csv: Fichier CSV contenant la liste des actions (nom, coût, retour sur investissement).
L'algorithme évalue toutes les combinaisons possibles d'actions et sélectionne celle qui offre le meilleur profit tout en respectant le budget.
- Charge toutes les actions depuis le fichier CSV.
- Génère toutes les combinaisons possibles d'actions.
- Filtre les combinaisons dépassant le budget.
- Trie les combinaisons restantes par profit décroissant.
- Retourne la combinaison optimale.
- Temporelle : ( O(2^n) ), où ( n ) est le nombre d'actions. Cela en fait une méthode coûteuse, particulièrement inefficace pour des jeux de données volumineux.
- Spatiale : Proportionnelle au nombre de combinaisons possibles.
- Garantit une solution optimale.
- Non scalable : inefficace pour de grands nombres d'actions ou budgets élevés.
Cet algorithme adopte une approche simplifiée et rapide : il trie les actions par leur rentabilité (profit/coût) et les sélectionne successivement jusqu'à épuisement du budget.
- Charge toutes les actions depuis le fichier CSV.
- Trie les actions par rentabilité décroissante.
- Ajoute les actions les plus rentables tant que le budget le permet.
- Retourne la combinaison d'actions choisie.
- Temporelle : ( O(n \log n) ) pour le tri + ( O(n) ) pour la sélection = ( O(n \log n) ).
- Spatiale : Proportionnelle au nombre d'actions.
- Rapide et efficace.
- Scalable pour de grands jeux de données.
- Ne garantit pas une solution optimale.
| Critère | Force Brute | Glouton |
|---|---|---|
| Complexité | ( O(2^n) ) | ( O(n \log n) ) |
| Optimalité | Toujours optimale | Pas toujours optimale |
| Performance | Lent pour ( n > 20 ) | Rapide et scalable |
| Utilisation mémoire | Élevée | Modérée |
- Python 3.x
- Fichier CSV avec les colonnes suivantes :
name,cost,return_on_investment.
- Cloner ce dépôt.
- Placer un fichier CSV nommé
actions_list.csvdans le même répertoire. - Exécuter l'un des scripts :
python bruteforce.pypython optimized.pyCe projet démontre deux approches opposées à un problème d'optimisation. La force brute est utile pour des petits ensembles où l'optimalité est cruciale, tandis que l'approche gloutonne est idéale pour des problèmes nécessitant des solutions rapides et approximatives.