Een verhuisfirma wil zo efficiënt mogelijk kunnen verhuizen. Deze firma heeft maar één soort van dozen en die heeft een maximaal volume dat het kan bevatten. De vakbond van verhuizers legt daarnaast een maximaal gewicht op dat een verhuizer mag dragen. De firma wil nu weten op welke manier ze de dozen moet vullen zodat ze het minst aantal dozen moeten gebruiken.

Gevraagd: ontwerp en implementeer een algoritme via branch-and-bound voor dit verhuisdozenprobleem. Implementeer hiervoor de interface VerhuisPlanner¹ in een klasse genaamd BBVerhuisPlanner. Hiervoor schrijf je een methode public List<VerhuisDoos> selecteer(Collection<VerhuisItem> items), die een collectie van items, van de gegeven klasse VerhuisItem², als argument heeft. De uitvoer is een lijst van de gegeven klasse VerhuisDoos³ waarbij elke doos een collectie van VerhuisItems bevat.

Het volume en het gewicht van elk VerhuisItem is genormaliseerd zodat het totale volume en het totale gewicht van een verhuisdoos maximaal 1 is. M.a.w. de som van het gewicht en de som van het volume van alle items in een doos mag niet meer dan 1 zijn. De dozen moeten zo gevuld worden dat het aantal dozen minimaal is. Als er meerdere oplossingen zijn, dan mag je er eender welke teruggeven.

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