Rucksackproblem mit exakt erforderlicher Artikelnummer

Question

Wie würden wir das Rucksackproblem lösen, wenn wir nun die Anzahl der Elemente im Rucksack mit einem konstanten $ L $ reparieren müssen?Dies ist das gleiche Problem (maximales Gewicht von $ W $ , jeder Artikel hat einen Wert $ V $ undGewicht $ W $ ), aber Sie müssen genau hinzufügen $ L $ Artikel(n) zum Rucksack (und müssen offensichtlich den Gesamtwert des Knapsacks optimieren).

Jede Weise, wie ich daran gedacht habe, diese bisher umzusetzen (dynamische Programmierung, Brute-Kraft), hat zu einem Ausfall oder die Rechenzeit der Lebensdauer der Universal-Ebene geführt.Jede Hilfe oder Ideen werden geschätzt.

edit: Ich suche nach Pseudo-Polynom-Zeitlösungen

Answer 1

Sie können dieses Problem in eine Instanz von Rucksack umwandeln. Lassen Sie $ n $ Seien Sie die Anzahl der Elemente, $ V $ Seien Sie der maximale Wert eines Artikels und vermuten dass jeder Artikel höchstens $ W $ wiegt (ansonsten kann es verworfen werden).

Um sicherzustellen, dass Sie mindestens $ L $ Elemente auswählen:

• fügen Sie $ n (v + 1) $ auf den Wert jedes Artikels.
• Nun ist das Problem, das der Maximierung der Anzahl der ausgewählten Gegenstände, die Bindungen zugunsten von Artikeln mit dem größten ursprünglichen Gesamtwert, der Gewichtsbeschränkungen, unterliegt. Es gibt eine Lösung, die zumindest $ L $ Elemente IFF auswählt, wobei die optimale Lösung einen Wert von mindestens $ n (v +1) L $ .

Um sicherzustellen, dass Sie höchstens $ L $ Elemente auswählen:

• fügen Sie $ (W + 1) $ zum Gewicht jedes Artikels.
• fügen Sie $ l (W + 1) $ auf $ W $ .
• Jetzt jede Teilmenge von mehr als $ L $ Elemente wiegt mindestens $ (L + 1) (W + 1 )= L (w + 1) + (w + 1)> l (w + 1) + w $ , und ist daher nicht machbar. Jede Teilmenge von $ L $ Elemente, die ein Gesamtgewicht von $ W $ W $ hatten, wiegt jetzt $ l (W + 1) + W $ , und daher ist das machbare IFF $ w \ le w $ . Eine Teilmenge mit weniger als $ L $ Elemente ist möglicherweise möglich, auch wenn das Gesamtgewicht mehr als $ W $ , jedoch ist der Gesamtwert immer kleiner als $ n (v + 1) L $ .