In het knapsack-probleem beschouwt men n objecten met gegeven gewichten \(g_0, ..., g_{n-1}\) en gegeven winsten \(w_0, ..., w_{n-1}\). Verder is ook de totale capaciteit \(M\) van de knapsack gegeven. Er wordt gevraagd om een deelverzameling van objecten te selecteren met een zo groot mogelijke totale winst, 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 DiscreteKnapsack¹ in een klasse genaamd DynamischDiscreteKnapsack. Hiervoor schrijf je een methode public Collection<KnapsackItem> selecteer(Collection<KnapsackItem> items, int M), die een collectie van items als argument heeft, alsook een capaciteit \(M\). De uitvoer is een deelverzameling van items die de totale winst maximaliseert zonder het maximale totale gewicht te overschrijden. Maak hierbij gebruik van de gegeven klasse 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 winst.

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.

Opmerking

Het is niet toegestaan om de input items van de methode selecteeraan te passen. Indien je dit wel doet, zal de test falen.