[Rucksackproblem (Wikipedia)](https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83 % E3% 82% AF% E5% 95% 8F% E9% A1% 8C) Gierige Methode (Wikipedia) Löse mit% B2% E6% B3% 95). Beachten Sie, dass die für die gierige Methode erforderliche Lösung nicht immer eine exakte Lösung ist. Wir würden uns freuen, wenn Sie uns mitteilen könnten, ob es Mängel oder Verbesserungsvorschläge bezüglich des Codes gibt.
(Über Gier Methode aus Wikipedia)
Ein Beispiel für die Anwendung auf das Rucksackproblem ist unten gezeigt. Im Fall dieses Problems kann es angewendet werden, indem jedes Gepäck aufgeteilt und bewertet wird.
Bestimmen Sie die Bewertung jedes Gepäckstücks im Rucksackproblem. Die Zahl (Wert) ÷ (Volumen) wird häufig verwendet.
Wählen Sie das Gepäck mit dem höchsten Bewertungswert.
Wenn das Gepäck die maximale Kapazität nicht überschreitet, auch wenn Sie es in den Rucksack stecken, legen Sie es in den Rucksack.
Wählen Sie das gesamte Gepäck in der Reihenfolge des Bewertungswerts aus und wiederholen Sie den obigen Vorgang.
Die optimale Lösung kann mit der gierigen Methode für dieses Problem nicht erhalten werden.
Es ist, als würde man den Wert pro Volumen berechnen und viel verpacken!
4*x1 + 5*x2 + x3 + 3*x4 <= 6
xi = 0 or 1 (i = 1, 2, 3, 4)
Unter den oben genannten Bedingungen
7*x1 + 8*x2 + x3 + 2*x4
Um zu maximieren( x1, x2, x3, x4 )Verwenden Sie die gierige Methode.
import numpy as np
from pandas import DataFrame
#Aus Einschränkungen
weights = np.array([4, 5, 1, 3])
#Aus der Zielfunktion
values = np.array([7, 8, 1, 2])
#Ein Array von x. Der Anfangswert ist alle 0. Bei Annahme auf 1 setzen.
results = np.array([0, 0, 0, 0])
#Berechnen Sie den Auswertungswert.
evaluates = values/weights
#In einem DataFrame zusammenfügen
target_df = DataFrame(np.c_[evaluates, weights, values, results], index=['x1', 'x2', 'x3', 'x4'], columns = ['evaluate', 'weight', 'value', 'result'])
#Sortieren Sie in absteigender Reihenfolge nach dem Wert von evaluieren
target_df.sort_values('evaluate', ascending=False)
#Die Summe der Gewichte der angenommenen Elemente. Anfangswert 0.
weight_sum = 0
#Drehen Sie die Schleife von der mit dem höchsten Bewertungswert
for index, target in target_df.iterrows():
#Wird nach dem Löschen der Einschränkungen übernommen
if weight_sum + target['weight'] <= 6:
weight_sum += target['weight']
target['result'] = 1
print(target_df)
print("---answer---")
print(target_df['result'])
sort Die DataFrame-Sortierung bestand aus "sort_values". Als ich versuchte, es mit "sort" zu machen, wurde ich "DEPRECATED". Reihenfolge in umgekehrter Reihenfolge mit "aufsteigend". pandas.DataFrame.sort
Als ich versuchte, nur mit numpy in umgekehrter Reihenfolge zu sortieren, wurde wie folgt vorgegangen.
import numpy as np
arr = np.array([[4, 2], [5, 2], [6, 4], [1, 3], [2, 3]])
arr = arr[ arr[:,0].argsort() ] #0. Sorte
arr = arr[::-1]
print(arr)
[[6 4]
[5 2]
[4 2]
[2 3]
[1 3]]
Es ist ein bisschen nervig. ..
evaluate weight value result
x1 1.750000 4.0 7.0 1.0
x2 1.600000 5.0 8.0 0.0
x3 1.000000 1.0 1.0 1.0
x4 0.666667 3.0 2.0 0.0
---answer---
x1 1.0
x2 0.0
x3 1.0
x4 0.0
Name: result, dtype: float64
Deshalb, ( x1, x2, x3, x4 ) = ( 1, 0, 1, 0 )
Recommended Posts