Variante des Rucksacks

Question

Ähnlich dem ursprünglichen Problem, ich habe einige Artikel (mit Gewicht und Wert) gegeben und sollte den Rucksack füllen, um maximalen Gesamtwert zu erhalten. In dieser Version des Algorithmus wird mir jedoch eine unbegrenzte Anzahl von Kopien jedes Elements zur Verfügung gestellt. Könnten Sie mir ein paar Ideen/Pseudocode vorschlagen?

Answer 1

Dies ist das unbeschränkte Rucksack-Problem, und es gibt viele Links da draußen. Einige können gehören:

• https://en.wikipedia.org/wiki/Knapsack_problem#Unbounded_knapsack_problem
• http://www.csegeek.com/csegeek/view/tutorials/algorithms/dynamic_prog/dp_part7.php
• http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/DynProg/knapsack2.html