Jérome PIVERT - 02/12/2014 Python 2.7.3 Ce README contient également (en bas) les réponses à différentes questions Ce programme permet de tester différentes stratégies pour résoudre le problème du sac à dos, il produit egalement des boxplots sur differentes statistiques de chaque strategies. Il prend peut prendre en compte des arguments tels que des fichiers en entrée ou en sortie ou encore une option pour exporter les données brutes vers un fichier. Le fichier créé lors de l'export peut être utilisé pour effectuer des analyses plus poussées (sous R par exemple) N.B. Les stratégies 3_bis et 5_bis sont de légères variantes (par curiosité) des stratégies 3 et 5 la stratégie 3_bis va remplir de haut en bas puis de bas en haut puis de haut en bas etc.. la stratégie 5_bis fait appel à la fonction getBoxSize() --> c'est plus lent en général usage: ./main.py [-h] [-i/--infile INFILE] [-o/--output OUTFILE] [-e/--export_raw] optional arguments: -h, --help show this help message and exit -o OUTFILENAME, --outfile OUTFILENAME specifier un fichier sortie, n'affiche rien dans la console (sortie par defaut) -i INFILENAME, --infile INFILENAME specifier un fichier en entree (ne fait pas de dico aleatoires) --export_raw, -e exporter les donnees brutes dans un fichier texte raw.txt, pas disponible pour les tests exemples: ./main.py -i listeObjetsControle.txt -o resume_strats.txt execution du programme sur le fichier donne et les resultats sont retournes dans le fichier donne ./main.py -e execution du programme sur la console et export des donnees brutes vers un fichier texte Liste des fichiers: main.py contient les principales fonctions du programme box_functions.py fonctions liées aux boites others.py diverses fonctions pour executer le prog, contient notamment les fonctions de stats strategies.py toutes les strategies classes.py COULEURS ! LE MONDE IL EST JOLI LE MONDE IL BÔ README.txt graphiques/ contient des graphiques fait sur 500 dicos aléatoires et servant d'exemples sorties_jerome/ contient différents fichier de sorties et de données brutes #################### Réponse au questions: #################### #Question 1: Nombre de configurations possibles: combinaison de 16000 dans 400 --> trop grand pour être calculé #Question 16: Complexité des stratégies: avec n: nombre d'éléments dans le dictionnaire, en considérant O(1) stratégie 1: O(n) stratégie 2: O(n) stratégie 3: O(nlog(n)) a cause du tri, on peut negliger log(n) -> O(n) stratégie 3bis: idem strat 3 stratégie 4: idem strat 3 stratégie 5: idem strat 3 stratégie 5bis: O(nlogn+n*k) k=nombre d'object dans une boite, négligeable --> O(nlog(n)) --> O(n)