%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Optimisation de problème/Optimisation de problème|Accueil · Optimisation de problème]] %% nav-fin %% # Atelier 1 - Poudre de perlimpinpin Cet atelier combine deux versions du problème du sac à dos : des objets indivisibles et des matières divisibles. Il s'appuie sur le chapitre [[Code et Développement/Programmation/Optimisation de problème/02_Le problème du sac à dos|Le problème du sac à dos]]. Énoncé repris de la Battle Dev Hello Works de novembre 2019 (isograd.com). Niveau : ★★★. ## Énoncé Une caverne contient des pierres précieuses et des poudres. Chaque pierre a une valeur en pièces d'or et un poids en grammes. Une pierre se prend entière ou pas du tout. Chaque poudre a un prix au gramme et une quantité disponible en grammes. Une poudre se prend en quantité quelconque, jusqu'à la quantité disponible. Une lampe peut contenir au plus C grammes. Il faut calculer la plus grande valeur que la lampe peut contenir. ### Format des données - Ligne 1 : trois entiers N, M et C. N est le nombre de pierres, M le nombre de poudres, C la contenance de la lampe en grammes. Chacun est compris entre 1 et 100. - Lignes 2 à N + 1 : la valeur (de 1 à 1000) et le poids (de 1 à C) de chaque pierre. - Lignes N + 2 à N + M + 1 : le prix au gramme (de 1 à 100) et la quantité disponible (de 1 à C) de chaque poudre. La sortie est la valeur maximale. ### Exemple ``` 2 2 100 600 40 1000 50 20 40 15 80 ``` La réponse est 1950. On prend la pierre de valeur 1000 (50 g), puis 40 g de la poudre à 20 pièces le gramme, puis 10 g de la poudre à 15 pièces le gramme : 1000 + 800 + 150 = 1950. ## Données Les quatre jeux de test sont chargés dans le dossier de Python de cette page. Le fichier `outputN.txt` contient la réponse attendue pour `inputN.txt`. ```sq-fichier nom: input1.txt --- 1 1 10 87 6 79 2 ``` ```sq-fichier nom: output1.txt --- 245 ``` ```sq-fichier nom: input2.txt --- 10 10 100 485 84 675 62 261 35 255 2 817 83 420 87 844 64 233 92 403 44 601 36 64 60 79 98 92 38 60 17 100 70 24 37 3 11 93 83 59 36 49 12 ``` ```sq-fichier nom: output2.txt --- 9859 ``` ```sq-fichier nom: input3.txt --- 3 10 2 97 2 555 1 834 2 25 1 9 1 47 2 86 1 14 1 1 1 1 1 98 1 36 2 39 1 ``` ```sq-fichier nom: output3.txt --- 834 ``` ```sq-fichier nom: input4.txt --- 100 100 100 680 100 899 79 770 89 925 96 82 87 220 1 217 84 95 24 515 51 80 41 836 23 858 19 882 85 230 29 106 85 722 83 537 29 636 87 8 95 255 7 694 63 447 51 447 10 112 16 494 10 664 44 754 68 190 71 598 23 810 21 679 75 825 10 289 80 60 3 585 97 240 1 764 69 184 99 794 47 720 80 896 2 293 55 824 95 722 46 29 30 981 15 648 78 288 18 568 59 964 57 756 62 497 42 51 59 388 100 376 12 391 57 548 95 710 88 344 86 344 90 640 86 583 34 708 53 669 75 731 55 413 93 490 11 851 61 538 80 498 1 463 68 894 2 447 76 324 100 287 97 455 5 721 90 488 93 617 24 512 73 751 35 989 21 997 22 114 19 8 80 783 48 202 31 564 28 587 95 881 96 901 79 863 95 266 19 395 5 521 4 978 47 881 34 786 6 852 49 233 27 33 86 68 41 78 35 63 1 97 80 100 72 70 63 17 94 85 96 32 90 74 35 60 32 43 1 72 70 75 61 76 50 54 83 69 63 8 65 77 59 73 11 29 83 43 41 16 92 95 81 25 35 5 18 78 13 67 97 76 37 57 99 3 64 67 92 65 80 69 76 89 31 20 64 71 4 15 76 32 72 1 23 84 100 73 100 59 65 76 59 56 58 17 84 69 36 57 38 63 69 10 7 12 29 32 92 16 98 88 50 68 30 37 84 91 64 68 80 96 83 25 73 85 72 39 49 64 40 18 50 77 27 33 40 70 34 12 52 34 3 24 6 6 59 12 86 86 82 56 91 86 86 35 100 77 44 34 92 70 94 45 64 5 2 100 4 83 99 41 35 93 56 65 88 27 36 27 61 33 91 1 27 74 76 34 45 83 64 51 27 13 52 2 22 84 4 94 83 10 91 ``` ```sq-fichier nom: output4.txt --- 12334 ``` ## Lire un fichier La fonction `lire` renvoie la liste des lignes non vides d'un fichier. Exécutez cette cellule avant les suivantes. ```sq-python def lire(nom): with open(nom) as f: return [ligne.strip() for ligne in f if ligne.strip()] exemple = ["2 2 100", "600 40", "1000 50", "20 40", "15 80"] for k in range(1, 5): print("Entrée", k, ":", lire("input" + str(k) + ".txt")[:4], "...") print("Sortie", k, ":", lire("output" + str(k) + ".txt")[0]) #--- sortie Entrée 1 : ['1 1 10', '87 6', '79 2'] ... Sortie 1 : 245 Entrée 2 : ['10 10 100', '485 84', '675 62', '261 35'] ... Sortie 2 : 9859 Entrée 3 : ['3 10 2', '97 2', '555 1', '834 2'] ... Sortie 3 : 834 Entrée 4 : ['100 100 100', '680 100', '899 79', '770 89'] ... Sortie 4 : 12334 ``` ## Question 1 : extraire les données Écrivez `extraire(lignes)`. La fonction renvoie la contenance `C`, la liste des pierres et la liste des poudres. Une pierre est un tuple `(valeur, poids)`. Une poudre est un tuple `(prix, quantite)`. ```sq-python def extraire(lignes): N, M, C = [int(x) for x in lignes[0].split()] pierres = [] poudres = [] # à compléter return C, pierres, poudres print(extraire(exemple)) #--- correction def extraire(lignes): N, M, C = [int(x) for x in lignes[0].split()] pierres = [tuple(int(x) for x in l.split()) for l in lignes[1:N + 1]] poudres = [tuple(int(x) for x in l.split()) for l in lignes[N + 1:N + M + 1]] return C, pierres, poudres print(extraire(exemple)) #--- tests assert extraire(exemple) == (100, [(600, 40), (1000, 50)], [(20, 40), (15, 80)]), "extraire(exemple) doit renvoyer (100, [(600, 40), (1000, 50)], [(20, 40), (15, 80)])" assert len(extraire(lire("input4.txt"))[1]) == 100, "input4.txt contient 100 pierres" #--- sortie (100, [(600, 40), (1000, 50)], [(20, 40), (15, 80)]) ``` ## Question 2 : remplir avec des poudres Une poudre se prend en quantité quelconque. Le meilleur remplissage d'une place donnée commence par la poudre de plus grand prix au gramme, puis passe à la suivante. Cette méthode gloutonne donne l'optimum, car chaque gramme est rempli avec le prix le plus élevé encore disponible. Écrivez `valeur_poudres(poudres, place)`, qui renvoie la valeur maximale de poudres pour une place de `place` grammes. ```sq-python def valeur_poudres(poudres, place): total = 0 # à compléter : parcourir les poudres par prix décroissant return total print(valeur_poudres([(20, 40), (15, 80)], 100)) print(valeur_poudres([(20, 40), (15, 80)], 50)) #--- correction def valeur_poudres(poudres, place): total = 0 for prix, quantite in sorted(poudres, reverse=True): prise = min(quantite, place) total += prix * prise place -= prise if place == 0: break return total print(valeur_poudres([(20, 40), (15, 80)], 100)) print(valeur_poudres([(20, 40), (15, 80)], 50)) #--- tests assert valeur_poudres([(20, 40), (15, 80)], 100) == 1700, "100 g : 40 g à 20 puis 60 g à 15, soit 1700" assert valeur_poudres([(20, 40), (15, 80)], 50) == 950, "50 g : 40 g à 20 puis 10 g à 15, soit 950" assert valeur_poudres([(20, 40)], 0) == 0, "sans place, la valeur est 0" #--- sortie 1700 950 ``` ## Question 3 : choisir les pierres Une pierre est indivisible. Le glouton ne donne plus l'optimum : c'est le sac à dos 0/1. La programmation dynamique le résout. Écrivez `meilleures_pierres(pierres, capacite)`. La fonction renvoie une liste `meilleur` de longueur `capacite + 1`. La case `meilleur[w]` contient la plus grande valeur de pierres dont le poids total ne dépasse pas `w`. Méthode : on part d'une liste de zéros. Pour chaque pierre `(valeur, poids)`, on parcourt `w` de `capacite` jusqu'à `poids`, en descendant, et on remplace `meilleur[w]` par `max(meilleur[w], meilleur[w - poids] + valeur)`. Le parcours descendant garantit que chaque pierre n'est prise qu'une fois. ```sq-python def meilleures_pierres(pierres, capacite): meilleur = [0] * (capacite + 1) # à compléter return meilleur m = meilleures_pierres([(600, 40), (1000, 50)], 100) print(m[40], m[50], m[90], m[100]) #--- correction def meilleures_pierres(pierres, capacite): meilleur = [0] * (capacite + 1) for valeur, poids in pierres: for w in range(capacite, poids - 1, -1): meilleur[w] = max(meilleur[w], meilleur[w - poids] + valeur) return meilleur m = meilleures_pierres([(600, 40), (1000, 50)], 100) print(m[40], m[50], m[90], m[100]) #--- tests assert meilleures_pierres([(600, 40), (1000, 50)], 100)[100] == 1600, "les deux pierres tiennent dans 100 g : 1600" assert meilleures_pierres([(600, 40), (1000, 50)], 100)[60] == 1000, "dans 60 g, seule la pierre de 1000 est prise" assert meilleures_pierres([(600, 40), (1000, 50)], 100)[39] == 0, "aucune pierre ne tient dans 39 g" #--- sortie 600 1000 1600 1600 ``` Le module `knapsack` fait le même calcul : `knapsack.knapsack(poids, valeurs).solve(capacite)` renvoie la valeur maximale et les indices des objets choisis, pour une seule capacité. ## Question 4 : combiner pierres et poudres Si les pierres choisies occupent au plus `w` grammes, la place restante `C - w` se remplit de poudres. La valeur totale vaut alors `meilleur[w] + valeur_poudres(poudres, C - w)`. La réponse est le maximum de cette somme pour `w` de 0 à `C`. Choisir d'abord les meilleures pierres pour toute la contenance, puis compléter avec des poudres, ne suffit pas : une pierre peut valoir moins que la poudre qui occuperait sa place. Écrivez `resoudre(lignes)`, puis vérifiez les quatre jeux de test. ```sq-python def resoudre(lignes): C, pierres, poudres = extraire(lignes) # à compléter return 0 print(resoudre(exemple)) for k in range(1, 5): print(k, resoudre(lire("input" + str(k) + ".txt")), lire("output" + str(k) + ".txt")[0]) #--- correction def resoudre(lignes): C, pierres, poudres = extraire(lignes) meilleur = meilleures_pierres(pierres, C) return max(meilleur[w] + valeur_poudres(poudres, C - w) for w in range(C + 1)) print(resoudre(exemple)) for k in range(1, 5): print(k, resoudre(lire("input" + str(k) + ".txt")), lire("output" + str(k) + ".txt")[0]) #--- tests assert resoudre(exemple) == 1950, "l'exemple de l'énoncé donne 1950" assert resoudre(lire("input1.txt")) == 245, "input1.txt donne 245" assert resoudre(lire("input2.txt")) == 9859, "input2.txt donne 9859" assert resoudre(lire("input3.txt")) == 834, "input3.txt donne 834" assert resoudre(lire("input4.txt")) == 12334, "input4.txt donne 12334" #--- sortie 1950 1 245 245 2 9859 9859 3 834 834 4 12334 12334 ``` ## À retenir - Les poudres relèvent du sac à dos fractionnaire : le glouton par prix au gramme est optimal. - Les pierres relèvent du sac à dos 0/1 : la programmation dynamique sur la capacité donne l'optimum en O(N × C). - La combinaison parcourt toutes les répartitions de la contenance entre pierres et poudres, soit C + 1 cas. - Avec C ≤ 100 et N ≤ 100, le calcul compte environ 10 000 opérations, alors que l'énumération des sous-ensembles de pierres en compterait 2^100. %% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Optimisation de problème/Optimisation de problème|Accueil · Optimisation de problème]] %% nav-fin %%