In het knapsack-probleem beschouwt men n objecten met gegeven gewichten
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
1 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 items
die de totale winst maximaliseert zonder het maximale totale gewicht te overschrijden. Maak hierbij gebruik van de gegeven klasse KnapsackItem
2. 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
Gebruik eventueel de testklasse SimpleTest
3 om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.
Het is niet toegestaan om de input items
van de methode selecteer
aan te passen. Indien je dit wel doet, zal de test falen.