In het knapzakprobleem 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 de discrete versie van het knapzakprobleem is het niet toegestaan om objecten gedeeltelijk te selecteren. Dit lijkt misschien een klein verschil in vergelijking met de rationale versie, maar maakt het probleem veel moeilijker. Het discrete probleem is NP-compleet terwijl de rationale versie optimaal opgelost kan worden met een eenvoudig gretig algoritme. Gelukkig kunnen we hetzelfde idee ook gebruiken om voor het discrete probleem een branch-and-bound algoritme op te stellen dat heel wat kan snoeien.

Gevraagd: ontwerp en implementeer een algoritme via branch-and-bound voor het discrete knapzakprobleem. Implementeer hiervoor de interface DiscreteKnapsack¹ in een klasse genaamd BBDiscreteKnapsack. Hiervoor schrijf je een methode public Collection<KnapsackItem> selecteer(Collection<KnapsackItem> items, double capaciteit), die een collectie van items, van de gegeven klasse KnapsackItem², als argument heeft, alsook een gegeven capaciteit (\(M\)). De uitvoer is een deelverzameling van items die de totale winst maximaliseert zonder het maximale totale gewicht te overschrijden.

Gebruik eventueel de testklasse SimpleTest³ om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.