Fast Approximation-Algorithmen für das Rucksackproblem und das Teilmengen-Summenproblem

Gegeben ist eine positive ganze Zahl M sowie n Paare positiver Ganzzahlen (p~, cD, , (p. , c.), die Summe ~p~ zu maximieren, unter den Nebenbedingungen ~c, < M und ~, = 0 oder 1. Dies ist das bekannte 0/1-Rucksackproblem. Ein Algorithmus wird präsentiert, der für jedes 0 < e < 1 eine approximate Lösung P findet, die (P* - P)/P* < ~ erfüllt, wobei P* die gewünschte optimale Summe ist. Darüber hinaus hat der Algorithmus für festes e eine Zeitkomplexität von O(n log n) und eine Raumkomplexität von O(n). Eine Modifikation des Algorithmus für das unbeschränkte Rucksackproblem, bei dem die ~,'s jede nichtnegative ganze Zahl sein können, führt zu einer Berechnungszeit von O(n). Ein linearer Algorithmus wird auch für eine spezielle Klasse von 0/1-Rucksackproblemen erhalten, die die Eigenschaft hat, dass p,/c, für alle 1 < z < n gleich ist. SCHLÜSSELWÖRTER UND PHRASE.