Der Wikipedia-Artikel über das Knapsack-Problem enthält drei Arten davon:
1-0 (ein Element eines Typs)
Begrenzt (mehrere Elemente eines Typs)
Unbegrenzt (unbegrenzte Anzahl von Elementen eines Typs)
Der Artikel enthält DP-Ansätze für 1. und 3. Problemtypen, aber keine Lösung für 2.
Wie kann der dynamische Programmieralgorithmus zum Lösen von 2. beschrieben werden?
Verwenden Sie die 0-1-Variante, aber ermöglichen Sie die Wiederholung eines Elements in der Lösung bis zu der Anzahl, die in seiner Begrenzung angegeben ist. Sie müssten einen Vektor pflegen, der angibt, wie viele Kopien jedes Elements Sie bereits in die Teillösung aufgenommen haben.
Ich habe einen Artikel zu Code Project gepostet, in dem eine effizientere Lösung für den begrenzten Rucksack diskutiert wird Algorithmus.
Aus dem Artikel:
%Vor%In der dynamischen Programmierlösung ist jede Position des m-Arrays a Teilproblem der Kapazität j. Im 0/1-Algorithmus für jedes Teilproblem Wir betrachten den Wert des Hinzufügens einer Kopie jedes Artikels zum Rucksack. Im folgenden Algorithmus betrachten wir für jedes Teilproblem den Wert das Hinzufügen des kleineren der Menge, die passt, oder die Menge für jeden Artikel verfügbar.
Ich habe auch den Code verbessert, damit wir bestimmen können, was in der optimierter Rucksack (im Gegensatz zu nur dem optimierten Wert).
Der Download im Code Project-Artikel enthält einen Testfall.
Wenn Sie beispielsweise einen begrenzten Rucksack mit {2 (2-mal), 4 (3-mal), ...} versuchen, entspricht das einem 1-0-Rucksack mit {2, 2, 4, 4, 4 ,. ..}.
Ich werde Ihnen vorschlagen, den Knapsack Fraction Greedy Method Algorithm zu verwenden. Seine Komplexität ist O (n log n) und einer der besten Algorithmen. Unten habe ich seinen Code in c # erwähnt.
%Vor%Tags und Links algorithm knapsack-problem