Projet

Créez un projet vscode pour mettre toutes vos programmes.

Créez un fichier données.py et placez y l'exemple du cours sous la forme d'une constante.

Créez un fichier fractionnel.py où vous écrirez le code de l'algorithme glouton trouvant le sac à dos fractionnel optimal.

Vous testerez votre code dans le fichier test_fractionnel.py

Exécutez l'algorithme glouton fractionnel avec l'EXEMPLE du fichier données.py.

Ajoutez au fichier données.py une fonction profit(sac_à_dos, produits) qui rend le profit réalisé pour le sac à dos et les produits en entrée.

Vous testerez cette fonction dans le fichier test_données.py.

Créez un fichier main_fractionnel.py dont l'exécution rende les données, le sac à dos et le profit pour l'exemple. Vous devez avoir quelque chose du genre en sortie :

Données :
{'nom': 'poudre 1', 'kg': 15, 'prix': 135}
{'nom': 'poudre 2', 'kg': 2, 'prix': 30}
{'nom': 'poudre 3', 'kg': 4, 'prix': 32}
{'nom': 'poudre 4', 'kg': 1, 'prix': 6}
{'nom': 'poudre 5', 'kg': 6, 'prix': 18}
{'nom': 'poudre 6', 'kg': 80, 'prix': 800}

Sac à dos fractionnel optimal :
0 poudre 1
1 poudre 2
0 poudre 3
0 poudre 4
0 poudre 5
0.225 poudre 6

Profit : 210.0

Créez un fichier sac_a_dos.py où vous écrirez le code de l'algorithme glouton trouvant le sac à dos.

Vous testerez votre code dans le fichier test_sac_a_dos.py

Créez un fichier main_sac_a_dos.py dont l'exécution rende les données, le sac à dos et le profit pour l'exemple. Vous devez avoir quelque chose du genre en sortie :

Données :
{'nom': 'poudre 1', 'kg': 15, 'prix': 135}
{'nom': 'poudre 2', 'kg': 2, 'prix': 30}
{'nom': 'poudre 3', 'kg': 4, 'prix': 32}
{'nom': 'poudre 4', 'kg': 1, 'prix': 6}
{'nom': 'poudre 5', 'kg': 6, 'prix': 18}
{'nom': 'poudre 6', 'kg': 80, 'prix': 800}

Sac à dos glouton :
1 poudre 1
1 poudre 2
0 poudre 3
1 poudre 4
0 poudre 5
0 poudre 6

Profit : 171

Dans le fichier données.py créez une fonction sac_à_dos(n, prix, K) qui génère aléatoirement un jeu de $n$ données où chaque donnée a un prix inférieure au paramètre prix et un poids inférieur à K

Dans un fichier aléatoire_glouton.py testez pour plusieurs jeux de donnés les différences entre :

• la valeur de la solution fractionnelle optimale,
• la valeur du glouton
• les différences entre les deux sac à dos

Dans un fichier efficace.py créez une fonction programmation_dynamique(produits, masse_totale) qui utilise la programmation dynamique pour trouver la valeur du sac à dos optimal.

Dans le fichier main_efficace.py, vérifiez que l'exemple donne bien la bonne valeur.

Dans un fichier aléatoire_valeur.py testez pour plusieurs jeux de donnés les différences entre :

• la valeur de la solution fractionnelle optimale,
• la valeur du glouton
• la valeur de la solution optimale (utilisez des valeurs de $K$ pas trop grande pour que le calcul par programmation dynamique soit possible en temps raisonnable)

Dans le fichier sac_a_dos.py créez une fonction énumération(produits, masse_totale) qui énumère tous les sac à dos possibles et rend le sac à dos maximum.

Vous testerez votre code dans le fichier test_sac_a_dos.py

Dans le fichier main_sac_a_dos.py, vérifiez que l'exemple donne bien le bon résultat.

Dans le fichier énumération.py créez une fonction branch_and_bound(produits, masse_totale) qui utilise le branch and bound pour trouver le sac à dos optimal.

Dans le fichier main_efficace.py, vérifiez que l'exemple donne bien la même valeure optimale pour le branch and bound et l'énumération.

• Faites en sorte de commencer avec le résultat de l'algorithme glouton plutôt que le sac à dos vide
• Faites le tri des produits une fois pour toute au début de la fonction branch_and_bound et pas à chaque appel du glouton fractionnel.

Dans un fichier aléatoire_temps.py, mesurez le temps pris par l'algorithme du branch and bound pour résoudre des problèmes avec :

• de plus en plus d'éléments mais un sac de capacité petite
• peux d'éléments mais un gros sac à dos (pour que la solution ne soit pas triviale, assurez vous que les poids des éléments soient grand...)

Implémentez l'algorithme à performance garantie et vérifiez que l'on est bien au pire deux fois moins bon que la solution optimale. Comparez son résultat à la solution optimale (calculée par branch and bound) et au résultat du glouton.

Implémentez un algorithme qui, à partir de la matrice rendue par l'algorithme de programmation dynamique, rend le sac à dos optimal associé.