Certains algorithmes ne permettent pas toujours d'obtenir le résultat optimal. Prenons le problème du sac à dos.

Un voleur doit amasser des objets de valeurs et les mettre dans son sac à dos ne supporte qu'une charge de 15 kg. Quels objets devra-t-il emporter pour partir avec la valeur la plus élevée ?

   

Une première solution consiste à calculer le rapport valeur/poids de chaque objet, puis de les amasser sans dépasser 15 kg.      

Cette méthode nous permet d'amasser 11$ pour un poids de 11 kg. Mais est-ce pour autant meilleure la solution ? Non trouvez la meilleure solution.

Pour résoudre ce problème avec un ordinateur, il faut explorer toutes les solutions possibles et retenir la meilleure :

10$ - 9kg	7$ - 12kg	1$ - 2kg	3$ - 7kg	2$ - 5kg	Valeur - poids
0	0	0	0	1	2$ - 5kg
0	0	0	1	0	3$ - 7kg
0	0	0	1	1	5$ 12kg
0	0	1	0	0	1$ - 2kg
...
1	0	0	0	0	10$ - 9kg
1	0	0	0	1	12$ - 14kg
1	0	0	1	0	13$ - 16kg

On remarque que le choix des objets se fait en utilisant un code binaire. Il y aura donc 2⁵ = 32 possibilités.

Dans ce cas de figure, l'ordinateur ne prendra pas beaucoup de temps à résoudre le problème parce qu'il n'y a pas beaucoup d'objets. La complexité en en O(2ⁿ) avec n étant le nombre d'objets. Le temps de calcul sera quand même doublé à chaque objet rajouté.

• Il faut connaître la valeur et le poids associé à chaque objet : un couple (un uplet ou tupple) ex : objet1=(10,9)
• Il faut mettre tous les objets dans une liste afin de les choisir par ordre binaire : objets = [(10,9),(7,12)...]
• Pour connaître le poids du sac à dos on a besoin d'une variable contenant la somme des poids des objets choisis.
• Pour connaître la valeur contenue dans le sac à dos on a besoin d'une variable contenant la somme des valeurs des objets choisis
• Un couple (valeur,poids) contenant la meilleure solution
  
• Et pour terminer il faut une valeur comprise entre 1 et 31 pour permettre de lister tous les choix possibles.

Début
objets ← [(10,9),(7,12),...]
vp_max ← (0,0)
pour i variant de 1 à 31
	vp ← (0,0)
	binaire ← format(i, '#010b')
	pour j variant de -1 à -5 inclus avec un pas de -1
		# additionner les tuples * poids binaire 
		vp ← tuple(map(sum,zip(vp,(objets[j][0]*int(binaire[j]),objets[j][1]*int(binaire[j])))))
	fin pour
	si la valeur du sac est supérieur à la valeur maxi et que le poids est inférieur ou égal à 15 kg
		vp_max ← vp
	fin si 
fin pour 
Affiche vp_max
fin

Traduire l'algorithme en langage python

Exécuter

Dans le jeu jumanji nos 4 aventuriers sont poursuivis par le chasseur Van Pelt. Il fait nuit noire et n'ont qu'une heure d'avance sur Van Pelt qui veut les éliminer.

Nos 4 aventuriers doivent traverser une passerelle en très mauvais état et ne possèdent qu'une seule torche pour s'éclairer. Vu l'état de la passerelle, seulement 2 aventuriers peuvent la traverser à la fois. L'un d'eux devra rapporter la torche pour faire traverser les suivants.

• Ruby Roundhouse connait très bien la passerelle et met 5 minutes pour la traverser
• Smolder Braveston est rapide et peut traverser le pont en 10 minutes
• Franklin "Mouse" Finbar et  Shelly Oberon ont le vertige et mettent respectivement 20 et 25 minutes pour traverser.

Dans quel ordre faudra-t-il faire passer nos aventuriers pour qu'ils ne se fassent pas tuer par le chasseur et pour qu'ils puissent couper la passerelle avant l'arrivée du chasseur.

Sans perdre de temps, Franklin "Mouse" Finbar sort une tablette de son sac, écrit quelques lignes de codes de programmation, introduit les données, lance le programme et leur annonce l'ordre de passage. Mais qu'a-t-il bien pu programmer ?

Voici son raisonnement :

Trois traversées sont nécessaires et il compte sur la vitesse de calcul du microprocesseur pour résoudre le problème par le hasard.

1. il prend au hasard deux personnes et les fait traverser.
   
2. il ajoute au temps de la traversée le temps de l'aventurier le moins rapide
3. on complète une variable de type chaine de caractère avec un texte indiquant qui a traversé
   
4. s'il reste des aventuriers à faire traverser :
   
1. au hasard, l'un d'entre eux revient
2. il ajoute au temps de la traversée le temps de l'aventurier qui effectue le retour
3. on complète une variable de type chaine de caractère avec un texte indiquant qui est revenu
   

4. on répète 3 fois à partir de 1
   
5. tant que la durée de la traversée n'est pas inférieur ou égale à 1h, on réinitialise toutes les variables et  on recommence à partir de 1
6. On affiche le résultat
   

• un dictionnaire avec le nom des aventurier et les temps de passages respectifs : personnages = {'Ruby':5,...}
• une liste depart contenant le nom des personnages voulant traverser la passerelle
• une liste arrivee contenant le nom des personnages qui ont traversé la passerelle
• une variable contenant le temps de la traversée
  

importer la bibliothèque random
personnages ← {'Ruby':5,'Smolder':10,'Franklin':20,'Shelly':25}
tps_traversee ← 100
tant que tps_traversee est supérieur à 60
    depart ← la liste des clés du dictionnaire # list(personnages.keys())
    mélanger la liste de départ
    arrivee ← []
    tps_traversee ← 0
    texte ← ""
    pour i variant de 0 à 3 exclus
        si le temps du premier personnage est supérieur au temps du second personnage pris dans la liste de départ
            ajouter au temps de la traversée le temps du premier personnage ayant pris le départ
        sinon
            ajouter au temps de la traversée le temps du second personnage ayant pris le départ
        fin si
        ajouter à la liste d'arrivée le nom du premier personnage
        ajouter à la liste d'arrivée le nom du second personnage
        enlever à la liste de depart le nom du dernier personnage arrivé         #indice -1
        enlever à la liste de depart le nom de l'avant dernier personnage arrivé    #indice -2
        ajouter à la variable texte  le nom des personnages ayant traversés et le temps déjà écoulé
        s'il y a encore des personnages dans la liste de départ:
            mélanger la liste arrivée
            ajouter à tps_traverse le temps du 1er personnage de la liste arrivee
            ajouter le nom du 1er personnage de la liste arrivee à la liste depart
            enlever le 1er personnage de la liste arrivee
            ajouter à la variable texte : le nom du personnage qui vient de traverser et le temps déjà écoulé
        fin si
    fin pour
fin tant que 
Afficher le texte constitué et "Smolder coupe les cordes de la passerelle"

Traduire l'algorithme en langage python, puis cliquez sur enregistrer:

Exécuter

Exécuter plusieurs fois le programme et mettre un compteur permettant de connaître la complexité.

Pourquoi le compteur ne donne-t-il pas toujours le même résultat ?

Combien y a-t-il de solutions possibles ? les quelles ?

Quelle est la condition d'arrêt du programme ?

Que se passe-t-il si je remplace tant que tps_traversee est supérieur à 60 par tant que tps_traversee est supérieur à 55