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

Recommended Posts

Un mémo qui a résolu le problème du sac à dos par la méthode gourmande
Résolvez le problème du sac à dos Python avec l'algorithme glouton
Faisons un robot qui résout le Rubik Cube! 2 Algorithme
Un mémo que j'ai touché au magasin de données avec python
Trouver une solution au problème N-Queen avec un algorithme génétique (2)
Faisons un robot qui résout le Rubik Cube! 3 Logiciel
Faisons un robot qui résout le Rubik Cube! 1. Vue d'ensemble
Trouver une solution au problème N-Queen avec un algorithme génétique (1)
Résolution du problème d'horaire des infirmières (optimisation des équipes) avec un algorithme génétique
J'ai créé un programme qui résout la recherche d'erreur en quelques secondes
Résolvez le problème du sac à dos Python avec la méthode de branche et liée
Une classe qui change librement la valeur de l'automate par communication socket
Illustration des résultats du problème du sac à dos
Un mémo organisé en renommant les noms de fichiers dans le dossier avec python
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (théorie)
Classe qui atteint l'API de DMM
Rechercher le labyrinthe avec l'algorithme python A *
AtCoderBeginnerContest154 Mémo de participation (Python, problème A ~ E)
Ecrire une méthode de cupidité simple en Python
[Python] Un programme qui arrondit le score
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (code Python)
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (résultat de l'exécution)
Solution au problème que vous ne pouvez pas activer en mettant conda dans pyenv
[Python] Solution au problème que les éléments sont liés lors de la copie d'une liste