Gegeven is een padgraaf met niet-negatieve gewichten op de toppen. Gevraagd is een deelverzameling van niet-adjacente toppen (m.a.w. een onafhankelijke verzameling) met maximum gewicht.

Ontwerp en implementeer een algoritme met dynamisch programmeren voor dit probleem.

Implementeer de interface PathGraph¹ in een klasse genaamd DynamicPathGraph. Schrijf een methode List<Integer> maximumIndependentSet(List<Integer> weights) die de gewichten op de toppen van een padgraaf krijgt en de indices van een maximum onafhankelijke deelverzameling teruggeeft.

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