In het knapsack-probleem beschouwt men \(n\) objecten met gegeven groottes \((w_1, \dots, w_n)\) en gegeven waarden \((v_1, \dots v_n)\). Verder is ook de totale capaciteit \(W\) van de knapsack gegeven. Er wordt gevraagd om een deelverzameling van objecten te selecteren met een zo groot mogelijke totale waarde, zodat het totale gewicht de capaciteit niet overschrijdt. In tegenstelling tot het rationale knapsack-probleem, is het bij het discrete knapsack-probleem niet toegelaten om objecten gedeeltelijk te selecteren.
In het specifieke geval dat alle gewichten en de capaciteit gehele getallen zijn, kan je met dynamisch programmeren een optimale oplossing vinden. In deze oefening beschouwen we het discrete knapsack-probleem met deze extra beperking.
Gevraagd: ontwerp en implementeer een algoritme via dynamisch programmeren voor het discrete knapsack-probleem waarbij de gewichten en capaciteit gehele getallen zijn. Implementeer hiervoor de interface IntegerKnapsack in een klasse genaamd DynamicIntegerKnapsack. Hiervoor schrijf je een methode public Collection<KnapsackItem> select(Collection<KnapsackItem> items, int capacity), die een collectie van items als argument heeft, alsook een capaciteit \(W\). De uitvoer is een deelverzameling van items die de totale waarde maximaliseert zonder het maximale totale gewicht te overschrijden. Maak hierbij gebruik van de gegeven record KnapsackItem. Een object van de klasse KnapsackItem stelt een item voor dat aan de knapsack kan toegevoegd worden. Elk item heeft een bepaald gewicht en een bepaalde waarde.
De uitvoeringstijd van het gezochte algoritme is \(O(Mn)\), dus voor beperkte capaciteit van de rugzak is deze aanpak behoorlijk snel.
Gebruik eventueel de testklasse SimpleTest om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.
Het is niet toegestaan om de input items van de methode selecteeraan te passen. Indien je dit wel doet, zal de test falen.