Inhalt
- Definition - Was bedeutet Rucksackproblem?
- Eine Einführung in Microsoft Azure und die Microsoft Cloud | In diesem Handbuch erfahren Sie, worum es beim Cloud-Computing geht und wie Microsoft Azure Sie bei der Migration und Ausführung Ihres Unternehmens aus der Cloud unterstützen kann.
- Techopedia erklärt das Knapsack-Problem
Definition - Was bedeutet Rucksackproblem?
Das Rucksackproblem ist ein Optimierungsproblem, das verwendet wird, um sowohl das Problem als auch die Lösung zu veranschaulichen. Der Name leitet sich von einem Szenario ab, in dem die Anzahl der Elemente, die in einem Rucksack mit fester Größe platziert werden können, beschränkt ist. Bei einer Reihe von Gegenständen mit bestimmten Gewichten und Werten ist es das Ziel, unter Berücksichtigung der Gewichtsbeschränkung des Rucksacks so viel Wert wie möglich in den Rucksack zu bringen.
Eine Einführung in Microsoft Azure und die Microsoft Cloud | In diesem Handbuch erfahren Sie, worum es beim Cloud-Computing geht und wie Microsoft Azure Sie bei der Migration und Ausführung Ihres Unternehmens aus der Cloud unterstützen kann.
Techopedia erklärt das Knapsack-Problem
Das Rucksackproblem ist ein Beispiel für ein kombinatorisches Optimierungsproblem, ein Thema in Mathematik und Informatik zum Finden des optimalen Objekts aus einer Menge von Objekten. Dies ist ein Problem, das seit mehr als einem Jahrhundert untersucht wurde und ein häufig verwendetes Beispielproblem bei der kombinatorischen Optimierung ist, bei dem ein Bedarf für ein optimales Objekt oder eine endliche Lösung besteht, bei der eine umfassende Suche nicht möglich ist. Das Problem liegt in realen Szenarien wie der Ressourcenzuteilung bei finanziellen Engpässen oder sogar bei der Auswahl von Anlagen und Portfolios. Es kann auch in Bereichen wie angewandte Mathematik, Komplexitätstheorie, Kryptographie, Kombinatorik und Informatik gefunden werden. Es ist mit Sicherheit das wichtigste Problem in der Logistik.
Im Rucksackproblem haben die angegebenen Artikel mindestens zwei Attribute: den Wert eines Artikels, der sich auf seine Wichtigkeit auswirkt, und das Gewicht oder Volumen eines Artikels, das seine Einschränkung darstellt. Da eine erschöpfende Suche nicht möglich ist, kann man die Probleme in kleinere Unterprobleme aufteilen und sie rekursiv ausführen. Dies nennt man eine optimale Unterstruktur. Es wird jeweils nur ein Artikel behandelt und das aktuelle Gewicht im Rucksack angezeigt. Der Problemlöser muss nur auf der Grundlage des Gewichts, das noch akzeptiert werden kann, entscheiden, ob er den Artikel nimmt oder nicht. Wenn es sich jedoch um ein Programm handelt, ist die Neuberechnung nicht unabhängig und würde Probleme verursachen. Hier können dynamische Programmiertechniken angewendet werden. Lösungen für jedes Unterproblem werden gespeichert, sodass die Berechnung nur einmal durchgeführt werden muss.