[PYTHON] Ein Memo, das das Rucksackproblem mit der gierigen Methode löste

Dies ist ein Memo, wenn das Rucksackproblem mit der gierigen Methode gelöst wird.

Gierige Rechtspolitik

Legen Sie zuerst diejenigen mit einem hohen Wert pro Volumen in den Rucksack, und diejenigen, die voll sind, sind die Lösung! Das ist die Politik im gierigen Gesetz des Rucksackproblems. Wenn Sie beispielsweise in Vorbereitung auf ein hartes Überleben so viele "Pferde" und "Zufriedenheitsriegel" wie Sie möchten, die beide fast das gleiche Volumen haben, in einen Rucksack packen können, können Sie den Rucksack mit "○" füllen. Nur die "Buchzufriedenheitsleiste" wird verpackt. Es basiert auf dieser Heuristik.

Hinweise zur Implementierung

Ich persönlich finde es bequem, einem Artikel einen Taple (Artikel, Wert, Volumen) zuzuweisen und ihn in einer Liste zu speichern. Mit anderen Worten, die Liste sieht folgendermaßen aus:

tuples = [ (Waren, Wert, Volumen), (Waren, Wert, Volumen), 　　　 : (Waren, Wert, Volumen) ]

Zum Beispiel beim Zugriff auf die Elemente eines Taples in einer Liste

** "Volumen" von Punkt "3" **

Beim Zugriff

tuples[2][2]

Sie können den Wert mit erhalten.

Code

knapsack_greedy.py

import numpy as np

C = 2             #Rucksackgröße
len = 10          #Anzahl der Teile
tuples = []       #(Index, Wert, Gewicht, Wert/Liste, um Gewicht zu halten)

#Gierige Lösung und ihre Initialisierung
sol = np.zeros(10)

#Initialisierung von Wert und Gewicht
values = np.random.rand(len)
costs = np.random.rand(len)


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

#Taple nach dem Sortieren
tuples_sorted = []
    
#Wert/Nach Volumen sortieren
for x,y,z,w in sorted(tuples,key=lambda x:x[3],reverse = True):
    tuples_sorted.append((x,y,z,w))

sum = 0         #Substitutionsvariablen

for i in range(len):
    #Legen Sie die Artikel mit dem höchsten Wert pro Volumen in den Rucksack
    sum+=tuples_sorted[i][2]
    if(sum < C):
        sol[tuples_sorted[i][0]]=1         #Einfügen, wenn die Kapazität nicht überschritten wird
    else:
        sol[tuples_sorted[i][0]]=0         #Ich kann es nicht einfügen, weil es die Kapazität überschreitet

print("Rucksackgröße"+str(C))
print("Wert")
print(np.round(values,3))
print("Gewicht")
print(np.round(costs,3))
print("Ausgewähltes Objekt")
print(sol)

sum_ = 0
for i in range(len):
    sum_ += sol[i]*costs[i]
    
print("Gesamtkapazität des ausgewählten Elements")
print(str(sum_))

Ausgabe

Rucksackgröße 2
Wert
[ 0.631  0.543  0.668  0.337  0.011  0.454  0.536  0.527  0.434  0.833]
Gewicht
[ 0.823  0.546  0.759  0.028  0.005  0.638  0.694  0.468  0.474  0.351]
Ausgewähltes Objekt
[ 0.  1.  0.  1.  1.  0.  0.  1.  1.  1.]
Gesamtkapazität des ausgewählten Elements
1.87266067297