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

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

Opgave

Schrijf een Python-functie WISPath(path:list) die een pad als parameter krijgt, en de indices van een maximale deelverzameling van onafhankelijke toppen teruggeeft.

Voorbeeld

>>> WISPath([1, 4, 5, 4, 2, 8, 1, 5, 2, 3, 4, 3, 10, 2])
[1, 3, 5, 7, 10, 12]