Faire d'une variable une constante

Faire d'une variable une constante - Python - Programmation

Marsh Posté le 21-10-2014 à 18:57:58    

Bonjour !
 
Drôle de titre pour un sujet, il est vrai, mais je n'arrive pas à reformuler mon souhait autrement.
Je m'explique : Je suis en train d'essayer de faire un algorithme sur python qui permet à Arthur de choisir les objets de plus grandes valeurs dans son sac-à-dos et de les mettre sans dépasser le poids qu'il ordonne. Chaque objet a une valeur et chaque valeur a une masse. Deux objets de même valeur ont des masses identitiques. Sacré Arthur !
 
J'ai donc fait ça :

Code :
  1. def sacados(M,l,s):         #l : liste des valeurs ; s = liste des masses
  2. d=0           #Initialement, le sac est vide
  3. n=l
  4. while d<M and len(l)>1:
  5.  a=max(l)
  6.  c=l.count(a)        #Compte le nombre de fois où le maximum apparait
  7.  i=0
  8.  while i<=len(n)-1:       #Retiens la masse corresspondante à l'objet de la plus haute valeur
  9.   if n[i]==a:
  10.    m=s[i]
  11.   i+=1
  12.  d=d+m*c         #Calcul la masse correspondante à l'ensemble des objets de plus haute valeurs mis tous ensemble
  13.  for j in range(c):
  14.   l.remove(a)
  15.  while d>M:        #Vérifie si tous les objets ensembles ne dépasse pas la masse totale autorisée
  16.    d=d-m*c       #Si oui, on enlève tous les objets du sac
  17.    c-=1        #On les remet tous en elevant un
  18.    d=d+m*c       #Calcul le nouveau poids
  19.  if c>0:
  20.   print("Arthur doit prendre",c,"objets de valeur",a)
  21. print("Le reste, Arthur ne doit pas le prendre." )


 
Ce que je souhaite faire, c'est ne pas faire varier n quand l diminue, sinon, ça ne marche pas.
Quelqu'un saurait-il comment faire ?
 
Merci beaucoup !

Reply

Marsh Posté le 21-10-2014 à 18:57:58   

Reply

Marsh Posté le 21-10-2014 à 21:47:36    

Ouch c'est un peu inbouffable. j'aimerai bien t'aider mais:

 

1/ tu pourrais donner un exemple des valeurs que tu passes a ta fonction et du résultat que tu souhaite avoir ? (c'est quoi M ?)

 

2/ ca serait peut etre bien de re-ecrire ton algo en utilisant de vrai noms de variables  et non une lettre.

 

Style: d -> poids_sac (enfin si j'ai bien compris) ou l -> valeurs_objet

 

Ca rendrait ton code BEAUCOUP plus clair, surtout si un jour toi (ou quelqu'un d'autre) doit le relire. (un peu de lecture sur le sujet http://sametmax.com/bien-nommer-se [...] n-python/)


Message édité par rage2000 le 21-10-2014 à 21:49:41
Reply

Marsh Posté le 23-10-2014 à 15:24:37    

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 :
  1. def sacados(poids_maximal,liste_de_valeurs,liste_des_masses):
  2. poids_actuel=0            #Initialement, le sac est vide
  3. liste_initiale_de_valeurs=liste_de_valeurs
  4. while poids_actuel<poids_maximal and len(liste_de_valeurs)>1:
  5.  maximum_de_la_liste=max(liste_de_valeurs)
  6.  compteur_de_maximum=liste_de_valeurs.count(maximum_de_la_liste)    #Compte le nombre de fois où le maximum apparait
  7.  i=0
  8.  while i<=len(liste_initiale_de_valeurs)-1:      #Retiens la masse corresspondante à l'objet de la plus haute valeur
  9.   if liste_initiale_de_valeurs==maximum_de_la_liste:
  10.    masse_correspondante=liste_des_masses[i]
  11.   i+=1
  12.  poids_actuel=poids_actuel+masse_correspondante*compteur_de_maximum   #Calcul la masse correspondante à l'ensemble des objets de plus haute valeurs mis tous ensemble
  13.  for j in range(compteur_de_maximum):
  14.   liste_de_valeurs.remove(maximum_de_la_liste)
  15.  while poids_actuel>poids_maximal:       #Vérifie si tous les objets ensembles ne dépasse pas la masse totale autorisée
  16.    poids_actuel=poids_actuel-masse_correspondante*compteur_de_maximum  #Si oui, on enlève tous les objets du sac
  17.    compteur_de_maximum-=1        #On les remet tous en en enlevant un
  18.    poids_actuel=poids_actuel+masse_correspondante*compteur_de_maximum  #Calcul le nouveau poids
  19.  if compteur_de_maximum>0:
  20.   print("Arthur doit prendre",compteur_de_maximum,"objets de valeur",maximum_de_la_liste)
  21. 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 :
  1. >>> sacados(12,[2,3,1,34,30,34,34,33,22,34],[20,19,1,2,4,2,2,3,6,2])
  2. Arthur doit prendre 4 objets de valeur 34
  3. Arthur doit prendre 2 objets de valeur 33
  4. Arthur doit prendre 1 objets de valeur 1
  5. Le reste, Arthur ne doit pas le prendre.


 
Or, j'ai :

Code :
  1. >>> sacados(12,[2,3,1,34,30,34,34,33,22,34],[20,19,1,2,4,2,2,3,6,2])
  2. Arthur doit prendre 4 objets de valeur 34
  3. Arthur doit prendre 2 objets de valeur 33
  4. 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
Reply

Marsh Posté le 23-10-2014 à 20:34:25    

Pour ta question 1 je la comprend toujours pas.
Pour la 2 non je crois pas.
 
Apres je trouve que le probleme: ton algo est complexe car tu pars avec des datas pas pratique.  
Je pense que la bonne solution est de d'abord traiter tes listes pour avoir un truc simple a manipuler.
 
Voila comment j'aurai codé ca de mon coté (idem j'aurai pu afficher a la volé le resultat, mais je préfère retrouver une organisation ou traitement de la data et affichage est séparé, le code est plus maniable le jour ou tu veux le modifier):

Code :
  1. def bag(max_weight, values, weights):
  2.     objs = [(value, weights[index]) for index, value in enumerate(values)]
  3.     objs.sort()
  4.     objs.reverse()
  5.    
  6.     bag_weight = 0
  7.     draft_bag = {}
  8.     actual_value = 0   
  9.     for object_value, object_weight in objs:
  10.         if bag_weight + object_weight <= max_weight:
  11.             bag_weight += object_weight
  12.             if object_value not in draft_bag:
  13.                 draft_bag[object_value] = 1
  14.             else:
  15.                 draft_bag[object_value] += 1
  16.            
  17.     bag = [(object_value, object_quantity) for object_value, object_quantity
  18.            in draft_bag.items()]
  19.     bag.sort()
  20.     bag.reverse()
  21.     for object_value, object_quantity in bag:
  22.         print("Artur doit prendre %i objects de valeur %i" % (object_quantity,
  23.                                                               object_value))
  24.     print("Le reste, Arthur ne doit pas le prendre." )
  25.     print("Au passage c'etait pas demandé, mais il reste %i kilo de libre "
  26.           "dans le sac" % (max_weight - bag_weight))

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed