Gegeven is de capaciteit W van een knapzak en een rij van n objecten met gewichten (w₁, …, w_n) en winsten (p₁, …, p_n). Gevraagd is een selectie van deze objecten te bepalen, zodanig dat de totale winst zo groot mogelijk is en het totale gewicht de capaciteit van de knapsack niet overschrijdt. Eigen aan het rationale knapsack-probleem, is dat er objecten gedeeltelijk aan de knapsack mogen toegevoegd worden.

Gegeven is een interface Knapsack¹. Het is de bedoeling dat jullie een klasse RationalKnapsack maken die deze interface implementeert. Hierin staat de methode public Map<KnapsackItem, Double> select(List<KnapsackItem> items, double capaciteit). Implementeer deze methode zodat een optimale oplossing bekomen wordt voor het rationale knapsack-probleem. Als input krijg je een lijst van items die elk een gewicht en een winst hebben, en ook de capaciteit van de knapsack. Zo een item wordt voorgesteld door een object van de klasse KnapsackItem². De output is een map die de items afbeeldt op een reëel getal tussen 0.0 en 1.0. Dit getal geeft aan in welke mate dit item geselecteerd werd: 0 betekent niet geselecteerd, 1 betekent volledig geselecteerd. Alles tussen 0 en 1 betekent gedeeltelijk geselecteerd. Een item dat niet geselecteerd werd, mag je ook weglaten uit de map.

Ontwerp een optimaal algoritme voor dit probleem met polynomiale uitvoeringstijd. Denk er goed over na of en waarom dit algoritme altijd de optimale selectie vindt en implementeer het.

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

Opmerking

Gelieve de input-lijst items niet aan te passen. Indien je dit toch doet, zullen de testen falen.