Suche maximale Auslastung für 0-1 Multidimensional Knapsack

Question

Die typische Zielfunktion von 0-1 Multidimensional Knapsack ist es, den Wert aller Gegenstände im Rucksack zu maximieren. Ein guter Algorithmus wurde hier im Stackexchange-Link bereitgestellt: 0-1 Multidimensional Knapsack.

Was aber, wenn meine objektive Funktion ist, so viele Gegenstände in den Rucksack wie möglich zu packen? Alle Teile haben gleiche Werte. Der Stackexchange-Post (Knapsack problem with all profits equal to 1) behauptet, dass ein eindimensionaler Rucksack mit gleichen Werten durch den Greedy-Algorithmus gelöst werden kann. Ist das wahr? Ich dachte, das 01-Rucksack-Problem sei NP-schwer, daher könnte der Greedy-Algorithmus nicht die optimale Lösung bieten.

Also meine Fragen sind zweiteilig? 1) Kann in diesem Fall eine optimale Lösung durch einen Greedy-Algorithmus gegeben sein? 01 Rucksack mit gleichen Werten 2) Wie implementiert man einen mehrdimensionalen Greedy-Algorithmus? der vi/wi ist ein Wert geteilt durch einen Vektor ...

Answer 1

1.) Das Rucksackproblem ist ein NP-schweres Problem. Kurz gesagt, nein, Sie können es nicht optimal mit einem Greedy-Algorithmus lösen. Stattdessen existieren heuristische Ansätze, die Sie sehr nahe bringen können.

2.) Im Fall von gleichen Gewinn Rucksack, wird dies wahrscheinlich zu einem einfachen Fach Verpackungsproblem degradieren. Wenn in diesem Zusammenhang alle Entscheidungen hinsichtlich des Gewinns gleich sind, müssen Sie sich wahrscheinlich auf einen anderen Aspekt des Problems konzentrieren, der wahrscheinlich etwas wie "Größe" ist. Wenn das der Fall ist, werden Sie jedes Mal das kleinste Element auswählen müssen - in diesem Fall ist ein gieriger Algorithmus wahrscheinlich ausreichend und kann erreicht werden, indem Sie einfach Ihre Auswahl durchsehen und das kleinste Element auswählen.

Es sollte beachtet werden, dass eine lineare Suche eine lästige Menge an Overhead zu Ihrem Programm hinzufügen kann, wenn es sehr oft wiederholt wird. Stattdessen sollten Sie in Erwägung ziehen, einen MIN-Heap zu verwenden, da dadurch der kleinste verfügbare Wert bei niedrigeren Rechenkosten erzielt wird.