Definiere das mathematische Modell für das Rucksackproblem in eigenen Worten
Zielfunktion: Maximiere den Nutzen, indem die Summe aus allen Werten der Gegenstände (pi) * die maximale Anzahl des Dazugehörigen Gegenstandes (xi)
Restriktionen:
Die summe aus Aus dem Raumverbrauch der Gegenstände (wi * xi) muss kleiner als der maximale Raum sein
Anzahl der gewählten Gegenstände müssen kleiner als die Erlaubte anzahl sein
die gegenstände müssen aus entweder Zi oder der Binärzahlen sein
Was ist das Verfahren bei dem Greedy- Algorythmus?
Sortiere lalle Gegenstände absteigend Ihrer Wertdichte ( Wert / Gewicht) und füge die Gegenstände gemäß der Reihenfolge ein, solange noch Platz ist
Um wie viel Prozent ist der Greedy Algorhytmus schlechter als die Optimale Lösung?
Last changed9 months ago
