On m'a posé le problème suivant et mon code est devenu un désordre horrible et je suis assez coincé.
On vous donne une allocation à dépenser dans certains magasins (quelque chose comme 15 $, juste un entier positif) Vous ne pouvez dépenser cet argent que sous deux conditions:
1) Vous achetez exactement un article dans chaque boutique.
2) Vous dépensez tout votre argent (il ne reste rien et aucune dette)
Trouvez toutes les façons possibles d'acheter des articles pour satisfaire ce qui précède.
En réalité, vous disposez d'un budget int et d'un tableau comme
9 et [[1,2,3], [0,5], [2,3,8]]
où chaque tableau interne répertorie les prix des articles dans une boutique. Il peut y avoir arbitrairement de nombreux magasins avec arbitrairement de nombreux articles. Les coûts ne peuvent pas être négatifs, mais ils peuvent être gratuits!
La solution attendue ici serait:
[[1,5,3], [2,5,2], [1,0,8]]
Comme chaque tableau contient un article de chaque boutique, chacun totalise 9, et toutes les possibilités sont présentes. Pour compliquer les choses, la vitesse est primordiale.
Voici mon code qui est tombé dans la folie et un manque presque complet de fonctionnalités:
def Stepper(bud,LOL):
n=len(LOL)
lasts=[]
indices=[0 for j in range(n)]
focus=0
funds=[0 for j in range(n+1)]
funds[0]=bud
sols=[]
moveable=[]
for j in range(n):
length=len(LOL[j])
if(length==0):
return []
lasts.append(length-1)
if(moveable==[]):
if(length==1):
funds[j+1]=funds[j]-LOL[j][0]
else:
moveable.append(j)
focus=j
while(moveable!=[]):
while(LOL[focus][indices[focus]] > funds[focus]):
indices[focus]+=1
if(indices[focus]==lasts[focus]):
if(moveable[-1]==focus):
moveable.remove(focus)
if(moveable==[]):
if(focus<n-1):
moveable.append(focus+1)
funds[focus+1]=funds[focus]-LOL[focus][indices[focus]]
#print(n,lasts,indices,focus,moveable,funds,sols)
if((funds[focus+1]!=0) and (focus<n-1)):
focus+=1
indices[focus]=0
else:
if(funds[focus+1]==0):
for j in range(focus+1,n):
indices[j]=lasts[j]
sols.append(list(indices))
if(moveable[-1]==n-1):
moveable.remove(n-1)
if(moveable!=[]):
focus=moveable[-1]
indices[focus]+=1
if(indices[focus]==lasts[focus]):
if(moveable[-1]==focus):
moveable.remove(focus)
if(moveable==[]):
if(focus<n-1):
moveable.append(focus+1)
funds[focus+1]=funds[focus]-LOL[focus][indices[focus]]
focus+=1
indices[focus]=0
return(sols)
où bud est le budget et LOL est la liste des listes (les magasins et les prix)
4 Réponses :
Voici un moyen simple, et probablement inefficace, de le résoudre.
In [70]: s = [[1,2,3],[0,5],[2,3,8]]
In [71]: n = 9
In [72]: for x in s[0]:
...: for y in s[1]:
...: for z in s[2]:
...: if x+y+z == n:
...: print(x,y,z)
...:
1 0 8
1 5 3
2 5 2
À partir de la première boutique, pour n'importe quelle option, itérer sur la boutique suivante, puis à nouveau, pour n'importe quelle option du deuxième magasin, parcourez les options du magasin suivant. Faites la somme de tous les prix et vérifiez si la somme est égale à 9.
Le nombre de boutiques est variable. Même en ignorant les problèmes d'efficacité, cette réponse ne prend en charge qu'un nombre fixe de magasins.
Si vous êtes autorisé à utiliser itertools
(1, 0, 8) (1, 5, 3) (2, 5, 2)
Sortie:
import itertools
x = [[1,2,3],[0,5],[2,3,8]]
combinations = list(itertools.product(*x))
for o in combinations:
if sum(o) == 9:
print(o)
Dépend de cette question.
C'est un problème de combinatoire. Quel article de la boutique 1 se combine avec quel article de la boutique 2 et quels articles uniques des boutiques 3 ... n ajouter à un certain nombre?
La bibliothèque standard de Python a une fonction qui peut générer toutes ces combinaisons pour vous, vous épargnant les boucles for imbriquées. C'est le itertools.product a >:
>>> list(filter(lambda prices: sum(prices) == budget, itertools.product(*shops)) [(1, 0, 8), (1, 5, 3), (2, 5, 2)]
Ensuite, nous voulons nous débarrasser de toutes les combinaisons qui ne satisfont pas à notre condition (que les prix correspondent exactement au budget total). Utilisons la fonction filter intégrée pour obtenir notre solution:
>>> import itertools >>> budget = 9 >>> shops = [[1, 2, 3], [0, 5], [2, 3, 8]] >>> list(itertools.product(*shops)) [(1, 0, 2), (1, 0, 3), (1, 0, 8), (1, 5, 2), (1, 5, 3), (1, 5, 8), (2, 0, 2), (2, 0, 3), (2, 0, 8), (2, 5, 2), (2, 5, 3), (2, 5, 8), (3, 0, 2), (3, 0, 3), (3, 0, 8), (3, 5, 2), (3, 5, 3), (3, 5, 8)]
Si vous êtes toujours intéressé par un algorithme, voici ma solution:
Stepper(9, [[1,2,3],[0,5],[2,3,8]])
Pour le tester, appelez simplement
def Stepper(bud, shops, combinations = None):
if combinations is None:
combinations = [[item] for item in shops[0]]
#if empty, populate the list of combinations with list containing every item of the first shop
shops = shops[1:] #remove the shop from the list
if len(shops) == 1: #if only one shop remains
counter = 0
while counter < len(combinations):
comb = combinations[counter] # take a combination
diff = bud - sum(comb) # check how much you have to spend
if diff in shops[0]:
#if the shop have what you're looking for you keep the combination
comb.append(diff)
counter += 1
else:
# there is no way to spend all the money
combinations.remove(comb)
return combinations
new_combinations = list()
for old_combination in combinations:
for item in shops[0]:
comb = old_combination + [item] #create every possible combination mixing the old combinations with the items of the next stop
if sum(comb) < bud: new_combinations.append(comb) # the combination is valid only if you have 0 or more money left
return Stepper(bud,shops[1:],new_combinations) # calculate combinations with the remaining shops
Salut, vous devez réaliser l'algorithme Tree Traversal Depth-first avec une vague du coin supérieur droit (premier prix du premier magasin) vers le bas à gauche (dernier prix du dernier magasin). Des principes communs bien décrits partout. En outre, les performances peuvent être considérablement augmentées en vérifiant le
soldeactuel (somme de tous les nœuds traversés) <=budget, donc quand il est dépassé, il vous suffit de sauter le parcours approfondi suivant qui ne peut pas être obtenu avec itertools.product.