7. házi feladat

LKR megszerkesztése:

Az előadáson bemutatott lkr.py módosítása úgy, hogy az LKR hossza mellett határozzunk meg egy konkrét közös részsorozatot, melynek hossza maximális. Ez történhet például úgy, hogy a c[i][j] értékek meghatározásakor feljegyezzük egy kétdimenziós tömbben, hogy a legjobb értéket honnan kaptuk. Miután c-t kitöltöttük, visszafelőlről meghatározható egy LKR.

Backtrack alkalmazása pénzváltásra:

A 8 vezér probléma megoldása alapján alkalmazzuk a backtrack algoritmust a pénzváltás problémára. A probléma a következő:
Adott S pénzösszeg és P = {p_1, ..., p_n} pozitív egészek esetén keresem az összes olyan S = {s_1, ..., s_n} nemnegatív szám n-est, melyre \sum_{x=1}^{n} pi*si egyenlő S-sel.