[PYTHON] Un mémo qui a résolu le problème du sac à dos par la méthode gourmande

Ceci est un mémo lors de la résolution du problème du sac à dos par la méthode gourmande.

Politique juridique cupide

Mettez d'abord ceux avec une valeur élevée par volume dans le sac à dos, et ceux qui sont pleins sont la solution! Telle est la politique de la loi avide du problème du sac à dos. Par exemple, pour vous préparer à une survie difficile, si vous pouvez mettre autant de "chevaux" et de "barres de satisfaction" que vous le souhaitez, les deux ayant presque le même volume, dans un sac à dos, vous pouvez remplir le sac avec "○". Seule la "barre de satisfaction du livre" sera emballée. Il est basé sur cette heuristique.

Notes sur la mise en œuvre

Personnellement, je trouve pratique d'attribuer une touche (élément, valeur, volume) à un élément et de le conserver dans une liste. En d'autres termes, la liste ressemble à ceci:

tuples = [ (Marchandises, valeur, volume), (Marchandises, valeur, volume), 　　　 : (Marchandises, valeur, volume) ]

Lors de l'accès aux éléments d'un taple dans une liste, par exemple

** "Volume" de l'élément "3" **

Lors de l'accès

tuples[2][2]

Vous pouvez obtenir la valeur avec.

code

knapsack_greedy.py

import numpy as np

C = 2             #Taille du sac à dos
len = 10          #Nombre d'objets
tuples = []       #(Index, valeur, poids, valeur/Liste pour tenir le poids)

#Solution gourmande et son initialisation
sol = np.zeros(10)

#Initialisation de la valeur et du poids
values = np.random.rand(len)
costs = np.random.rand(len)


#(Index, valeur, volume, valeur/le volume)
for i in range(len):
    tuples.append((i,values[i],costs[i],float(values[i]/costs[i])))

#Tapez après le tri
tuples_sorted = []
    
#valeur/Trier par volume
for x,y,z,w in sorted(tuples,key=lambda x:x[3],reverse = True):
    tuples_sorted.append((x,y,z,w))

sum = 0         #Variables de substitution

for i in range(len):
    #Mettez les articles avec la valeur par volume la plus élevée dans le sac à dos
    sum+=tuples_sorted[i][2]
    if(sum < C):
        sol[tuples_sorted[i][0]]=1         #Insérer si la capacité n'est pas dépassée
    else:
        sol[tuples_sorted[i][0]]=0         #Je ne peux pas le mettre car il dépasse la capacité

print("Taille du sac à dos"+str(C))
print("valeur")
print(np.round(values,3))
print("poids")
print(np.round(costs,3))
print("Élément sélectionné")
print(sol)

sum_ = 0
for i in range(len):
    sum_ += sol[i]*costs[i]
    
print("Capacité totale de l'élément sélectionné")
print(str(sum_))

production

Sac à dos taille 2
valeur
[ 0.631  0.543  0.668  0.337  0.011  0.454  0.536  0.527  0.434  0.833]
poids
[ 0.823  0.546  0.759  0.028  0.005  0.638  0.694  0.468  0.474  0.351]
Élément sélectionné
[ 0.  1.  0.  1.  1.  0.  0.  1.  1.  1.]
Capacité totale de l'élément sélectionné
1.87266067297