Rucksackproblem – Algorithmus in Python (Rucksackproblem)

Das algorithmische Rucksackproblem (und seine Python-Implementierung) ist interessant und Teil des ersten Digital- und Informatikprogramms.

Dieses Problem zeigt gierige Algorithmen, die alle Möglichkeiten zur Lösung eines Problems auflisten, um die beste Lösung zu finden.

Das Problem des Python-Algorithmus-Rucksacks ist ein Optimierungsproblem, dh eine Funktion, die maximiert oder minimiert werden muss, und Einschränkungen, die erfüllt sein müssen.

Das Rucksackproblem – Python-Algorithmus

Für einen Rucksack mit maximaler Kapazität von P- und N-Artikeln mit jeweils eigenem Gewicht und einem festgelegten Wert verwerfen Sie die Artikel im Rucksack, damit der endgültige Inhalt den maximalen Wert hat.



Beispielanweisung:

Maximale Rucksackkapazität: 11 Einheiten Anzahl der Artikel: 5 Artikelwerte: {10,50,20,30,60} < li> Gewicht der Objekte: {1,5,3,2,4}

Was ist der maximale Wert, der unter Berücksichtigung der maximalen Kapazitätsbeschränkung der Tasche von 11 in den Rucksack gesteckt werden kann?

Gieriger Algorithmus Python

Eine effiziente Lösung ist die Verwendung eines gierigen Algorithmus. Die Idee ist, das Wert / Gewichts-Verhältnis für jedes Objekt zu berechnen und das Objekt basierend auf diesem berechneten Verhältnis zu sortieren.

Wir nehmen das Objekt mit dem höchsten Verhältnis und fügen hinzu, bis wir nicht mehr hinzufügen können.

In der Bruchversion ist es möglich, dem Rucksack Artikelbrüche hinzuzufügen.

Implementierung eines Python-Rucksackproblems – nicht fraktionierte Version

Hier ist eine Implementierung des Problems des Python-Rucksacks in einer nicht fraktionierten Version, dh man kann keinen Bruchteil eines Objekts in die Tasche einfügen. Es können nur ganze Objekte hinzugefügt werden.



Klasse BagObject:
def init (Selbst, Gewicht, Wert, Index):
self.index = index
Selbstgewicht = Gewicht
self.value = value
self.report = value // weight
#Funktion für den Vergleich zwischen zwei BagObjects
# Wir vergleichen das berechnete Verhältnis, um sie zu sortieren
def lt (selbst, andere):
Selbstbericht zurückgeben & lt; other.report def getMaxValue (Gewicht, Werte, Kapazität):
arraySort = []
für i im Bereich (len (Gewicht)):
arraySort.append (BagObject (Gewicht [i], Werte [i], i)) # Sortieren Sie die Elemente der Tasche nach ihrem Bericht arraySort.sort (reverse = True) counterValue = 0 für Objekt in arraySort: currentWeight = int (object.weight) currentValue = int (object.value) wenn Kapazität - aktuelles Gewicht> = 0: # Wir fügen das Objekt in die Tasche # Wir subtrahieren die Kapazität Kapazität - = aktuelles Gewicht counterValue + = currentValue # Wir addieren den Wert in der Tasche return counterValue Gewicht = [1,5,3,2,4]
Werte = [10,50,20,30,60]
Kapazität = 11
maxValue = getMaxValue (Gewicht, Werte, Kapazität)
print (“Maximaler Wert im Rucksack =”, maxValue)

Das Ergebnis ist das Folgende:

py sacados.py
Maximaler Wert im Rucksack = 120

Implementierung des Python-Rucksackproblems – Teilversion

In der Bruchversion des Python-Rucksack-Agorithmus können Sie dem Rucksack Objektbrüche hinzufügen.

Klasse BagObject:
def init (Selbst, Gewicht, Wert, Index):
self.index = index
Selbstgewicht = Gewicht
self.value = value
self.report = value // weight
#Funktion für den Vergleich zwischen zwei BagObjects
# Wir vergleichen das berechnete Verhältnis, um sie zu sortieren
def lt (selbst, andere):
Selbstbericht zurückgeben & lt; other.report def getMaxValue (Gewicht, Werte, Kapazität):
arraySort = []
für i im Bereich (len (Gewicht)):
arraySort.append (BagObject (Gewicht [i], Werte [i], i)) # Sortieren Sie die Elemente der Tasche nach ihrem Bericht arraySort.sort (reverse = True) counterValue = 0 für Objekt in arraySort: currentWeight = int (object.weight) currentValue = int (object.value) wenn Kapazität - aktuelles Gewicht> = 0: # Wir fügen das Objekt in die Tasche # Wir subtrahieren die Kapazität Kapazität - = aktuelles Gewicht counterValue + = currentValue # Wir addieren den Wert in der Tasche sonst: Bruch = Kapazität / aktuelles Gewicht counterValue + = currentValue * Bruch Kapazität = int (Kapazität - (Gewicht Strom * Bruchteil)) brechen return counterValue Gewicht = [1,5,3,2,4]
Werte = [10,50,20,30,60]
Kapazität = 11
maxValue = getMaxValue (Gewicht, Werte, Kapazität)
print (“Maximaler Wert im Rucksack =”, maxValue)

Das Ergebnis ist das Folgende:

py sacados.py
Maximaler Wert im Rucksack = 140,0

Python-Algorithmus für interne Links:

https://128mots.com/index.php/category/python/
https://128mots.com/index.php/2021/01/21/algorithme-glouton-python/ https://128mots.com/index.php/2021/01/21/algorithme-glouton-python/ https://128mots.com/index.php/2021/01/19/levenshtein-python/ https://128mots.com/index.php/2021/01/19/levenshtein-python/ https://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/ https://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/
Python-Algorithmus für externe Links:

http://math.univ-lyon1.fr/irem/IMG/pdf/monnaie .pdf

http://www.dil.univ-mrs.fr/ ~ gcolas / algo-license / slide / gloutons.pdf

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *