So realisieren Sie einen anwendbaren Meet-in-the-Middle-Algorithmus für 0-1 Rucksack?

Question

Ich studiere jetzt Rucksackproblem (KP) und finde den in Wikipedia ein wenig unklar, wie er es in der theoretischen Zeitkomplexität von $ o ^ * (2 ^ {n / 2}) $ ? Ich kann den Algorithmus für das Problem der Subset-Summen (SSP) verstehen, das eine bestimmte Instanz von 0-1 kP ist, aber für das verallgemeinerte Problem kann es mit dem Schritt etwas nicht stimmt:

generasacodicetagpre.

Wie ich verstehe, ist dies zu suchen (z. B. binäre Suche) auf kombinierten Gewichten aller Teilmengen von B, die für jede Suche logarithmus Zeit nimmt. Aber nachdem wir wissen, welche Subsets weniger als W kombiniert haben, wie Sie den größten Wert finden? Wenn Sie nach Werten der Teilmengen mit Gewicht $ O ^ * (2 ^ {n / 2}) $ , aber so etwas wie $ o ^ * (2 ^ n) $ .

Selbst wenn es anfängt, die Subset des größten Werts (einfach für einen Tisch) zuerst ohne Einschnürung des kombinierten Gewichts zu finden, wird danach die Überprüfung des Gewichts wahrscheinlich falsch drehen und somit sind mehr Tests für andere Teilmengen erforderlich, von denen die Nummer scheint wieder mit der Tabellengröße zugeordnet zu sein.

Jetzt kann ich nur annehmen, dass der Gesamtwert und das kombinierte Gewicht stark positiv korreliert sind, so dass nach der Suche nach der Subset mit maximal zulässigen Gewicht nur ständige Zeit dauert, um diese Teilmenge für den exakten größten Wert zu suchen. Aber ich bin mit dieser Erklärung nicht zufrieden. Also hat jemand bessere Ideen zu diesem Thema?

ps: Ich habe das Originalpapier von Horowitz, Ellis und Sahni, Sartaj, gelesen, aber ich fand das definierte Problem, das dort ein Entscheidungsproblem anstelle des gemeinsamen Optimierungsproblems besteht. Vielleicht kann jemand Ideen in diese Richtung bereitstellen.

Answer 1

zuerst die Gewichte jeder Teilmenge von $ B $ vorkomput.

sortieren Sie sie nach Gewicht und legen Sie die Gewichte und Untermengen in parallele Arrays, sodass $ W [I]= Weight $ und $ S [i]= Subset $ .

Erstellen Sie dann ein anderes paralleles Array, so dass $ BEST [i] $ der Index $ J $ ist>der Menge des größten Werts derart, dass $ j <= I $ .Sie können dies mit einem einzelnen Scan von $ i= 0 $ nach oben machen, und erinnern Sie sich an den größten Wert, der bisher in jedem Schritt angesehen wird.

Jetzt, um $ B $ , mache Sie eine binäre Suche in $ W $ , um zu findenDas maximal zulässige Gewicht und das beste Set aus demselben Index in $ BEST $