Dynamic Programming Let G = (V, E) be a line graph such that V = {v1, v2, · · · , vn} and for every i, 1 ≤ i < n − 1, there is an edge ∈ E from vi to vi+1. Each vertex v has a non-negative weight w(v). A set S ⊆ V is an Independent Set if for every x, y ∈ S, there is no edge from x to y in G. The weight of an independent set S is X v∈S w(v) Give a dynamic programming based algorithm to compute a maximum weight independent set. Your solution must give the recurrence relation that captures the weight of maximum weight independent set and describe an iterative algorithm based on the recurrence relation. No credit is given if your solution does not describe the recurrence relation or uses a recursive algorithm. Part of the grade depends on efficiency.

Petrică, tânăr licean în clasa a ix-a, a primit în dar de la părinţii săi un cont bancar pentru micile sale cheltuieli curente. el este pasionat de internet banking şi îşi verifică cu grijă toate tranzacţiile efectuate. pentru creşterea securităţii tranzacţiilor online, banca îi furnizează lui petrică un număr pe care el va trebui să îl modifice, obţinând un număr tan – număr de autentificare a tranzacţiei (transaction authentication number). regula de obţinere a numărului tan este următoarea: se formează cel mai mic număr par din toate cifrele numărului furnizat de bancă. cerinţă cunoscând numărul n furnizat de bancă, să se determine numărul tan obţinut de petrică. date de intrare fişierul tan.in conţine pe prima linie numărul natural n cu semnificaţia din enunţ. date de ieşire fişierul de ieşire tan.out va conţine o singură linie pe care va fi scris numărul tan cerut. restricţii • 0 < n < 18*1018 • n are cel puţin o cifră pară • numărul tan obţinut nu poate conţine zerouri nesemnificative