carles12 | Bonjour rage2000 et merci de ta réponse.
Comme tu me l'as demandé, j'ai donné de vrais noms de variables à mon algorithme. Attention, il est, selon moi, encore plus "inbouffable", comme tu le dis. J'y ai mis un peu de couleur, comme il est présenté sur Python, pour y voir un peu plus clair.
Le voici :
Code :
- def sacados(poids_maximal,liste_de_valeurs,liste_des_masses):
- poids_actuel=0 #Initialement, le sac est vide
- liste_initiale_de_valeurs=liste_de_valeurs
- while poids_actuel<poids_maximal and len(liste_de_valeurs)>1:
- maximum_de_la_liste=max(liste_de_valeurs)
- compteur_de_maximum=liste_de_valeurs.count(maximum_de_la_liste) #Compte le nombre de fois où le maximum apparait
- i=0
- while i<=len(liste_initiale_de_valeurs)-1: #Retiens la masse corresspondante à l'objet de la plus haute valeur
- if liste_initiale_de_valeurs==maximum_de_la_liste:
- masse_correspondante=liste_des_masses[i]
- i+=1
- poids_actuel=poids_actuel+masse_correspondante*compteur_de_maximum #Calcul la masse correspondante à l'ensemble des objets de plus haute valeurs mis tous ensemble
- for j in range(compteur_de_maximum):
- liste_de_valeurs.remove(maximum_de_la_liste)
- while poids_actuel>poids_maximal: #Vérifie si tous les objets ensembles ne dépasse pas la masse totale autorisée
- poids_actuel=poids_actuel-masse_correspondante*compteur_de_maximum #Si oui, on enlève tous les objets du sac
- compteur_de_maximum-=1 #On les remet tous en en enlevant un
- poids_actuel=poids_actuel+masse_correspondante*compteur_de_maximum #Calcul le nouveau poids
- if compteur_de_maximum>0:
- print("Arthur doit prendre",compteur_de_maximum,"objets de valeur",maximum_de_la_liste)
- print("Le reste, Arthur ne doit pas le prendre.")
|
J'y ai pris un exemple simple avec 12 objets à sa disposition :
4 objets de valeur 34 qui pèse 2 chacun
1 objet de valeur 33 qui pèse 3
1 objet de valeur 30 qui pèse 4
1 objet de valeur 22 qui pèse 6
1 objet de valeur 3 qui pèse 19
1 objet de valeur 2 qui pèse 20
1 objet de valeur 1 qui pèse 1
Le sac d'Arthur peut contenir un poids total de 12.
Arthur veut prendre un maximum d'objet de plus grande valeur. Il va donc prendre les 4 objets de valeur 34, l'objet de valeur 33. Son sac pèse alors 11. Il peut encore rentrer l'objet de valeur 1 qui pèse 1.
Je devrai donc avoir :
Code :
- >>> sacados(12,[2,3,1,34,30,34,34,33,22,34],[20,19,1,2,4,2,2,3,6,2])
- Arthur doit prendre 4 objets de valeur 34
- Arthur doit prendre 2 objets de valeur 33
- Arthur doit prendre 1 objets de valeur 1
- Le reste, Arthur ne doit pas le prendre.
|
Or, j'ai :
Code :
- >>> sacados(12,[2,3,1,34,30,34,34,33,22,34],[20,19,1,2,4,2,2,3,6,2])
- Arthur doit prendre 4 objets de valeur 34
- Arthur doit prendre 2 objets de valeur 33
- Le reste, Arthur ne doit pas le prendre.
|
Alors j'ai réfléchi, et mon erreur vient du fait que la liste_initiale_de_valeurs devient de plus en plus petit quand la liste_de_valeurs devient de plus en plus petit. Du coup, ma deuxième boucle while est fausse.
J'ai alors deux questions :
1) Est-ce qu'il existe une fonction dans Python pour fixer la variable liste_initiale_de_valeurs pour qu'elle na varie jamais ?
2) Si la réponse à la première question est négative, existe-t-il une fonction ou un moyen simple de prendre le 2ème (ou 3ème, 4ème...) maximum d'une liste ?
Exemple : l=[1,2,5,3] . max(l)=5 , deuxièmemax(l)=3
Merci beaucoup !
_____________________________________________________________________________________
EDIT LE 23/10/2014 A 18h17 :
J'ai réussi à contourner le problème, mon algorithme tourne. Toutefois, si vous avez des réponses à ma première question, je suis preneur !
Merci !
Message édité par carles12 le 23-10-2014 à 18:17:46
|
