Rekursive Bounded Rucksack-Algorithmus

Question

Ich habe mit der Übersetzung der dynamischen Programmierung rekursive Rucksack Problem 0-1 zu einem dynamischen begrenzten rekursiven Rucksack kämpfen. Die Formel i zur Zeit in R mit bin, ist:

F(i,k)=max(v[i]+F(i-1, k-w[i]), F(i-1, k)) 

so jetzt frage ich mich, was diese Funktion für ein beschränktes dynamischen Knapsackproblems werden würde

danke

Answer 1

Die einfachste Modifizierung - erforderlich machen Anzahl der wiederholten Elemente

{3x1,2x5}=>{1,1,1,5,5} 

Ein anderer Ansatz - Erstellen Array/Vektor mit Anzahl der Kopien und verwenden Sie es in rekursiven c alls, um nur Einträge mit Nicht-Null-Kopienanzahlen zu prüfen