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.
We werken hier nu met groottes die niet altijd gehele getallen zijn, een dynamisch programmeren aanpak lukt dus niet. Dit probleem is NP-compleet terwijl de rationale versie optimaal opgelost kan worden met een eenvoudig gretig algoritme. Gelukkig kunnen we dit algoritme gebruiken om een grens uit te komen voor een optimale oplossing. Deze kunnen we dan gebruiken in een branch-and-bound algoritme.
Gevraagd: ontwerp en implementeer een algoritme via branch-and-bound voor het discrete knapsack-probleem waarbij de gewichten en capaciteit gehele getallen zijn. Implementeer hiervoor de interface DiscreteKnapsack in een klasse genaamd BBDiscreteKnapsack. Hiervoor schrijf je een methode public Collection<KnapsackItem> select(Collection<KnapsackItem> items, double 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.
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.