Dinamikus programozás II
Feladatok:
1. Adott egy n elemű számsorozat az a[0..n-1] tömbben. Írjunk programot, mely meghatározza a leghosszabb, szigorúan növekvő részsorozatát. Részsorozat alatt nem feltétlenül összefüggő karaktersorozatot értünk.( Pszeudokód )
2. Adott két számsorozat az a[1..n] és a b[1..m] tömbökben. Írjunk programot, mely meghatározza a leghosszabb közös részsorozatukat.( Pszeudokód )
3. Adott egy H cm hosszú polc és n könyv, amelyeknek ismert a vastagságuk cm-ben. Legyen az i-edik könyv vastagsága vi, ahol i = 1 ... n. Írjunk programot, mely meghatározza, hogy milyen könyveket tegyük fel a polcra, ha teljesen meg szeretnénk tölteni a polcot, a lehető legtöbb könyvet használva?

1.
    // a tömb feltöltése
          c[n] = 0
minden i = n-1 .. 0, végezd
c[i] = 0
minden j = i+1 .. n végezd
    ha a[i] < a[j] és c[i] < c[j] akkor c[i] = c[j]
    vége ha
    vége minden
    c[i] = c[i]+1
vége minden
kiírás  "A leghosszabb szigorúan növekvő részsorozat hossza:" m = max(c), pozíciója: mp

// tömbeli elemek kiertekelese: a részsorozat meghatározása
u = mp
kiiras a[u]
minden i = u + 1 .. n végezd
    ha a[u] < a[i] és c[i] == c[u] - 1 akkor
        kiírás a[i]
        u = i
    vége ha
vége minden

példa1:
a = {3,10,12,5,8,6,20,11};
kimenet:
c = {4,3,2,3,2,2,1,1}
a részsorozat hossza: 4
a részsorozat: {3, 10, 12, 20}

példa2:
a = {8,3,5,11,6,20,32,4,13,17,9,2,15};
kimenet:
c = {4,5,4,3,3,2,1,3,2,1,2,2,1}
a részsorozat hossza: 5
a részsorozat: {3, 5, 11, 20, 32}
2.
// inicializálás
minden i = 0 .. n végezd
    c[i][m]=0
vége minden
minden j = 0 .. m végezd
    c[n][j]=0
vége minden

// a tömb feltöltése 
minden i = n-1 .. 0 végezd
    minden j = m-1 .. 0 végezd
        ha a[i] == b[j] akkor c[i][j] = c[i+1][j+1]+1
        különben
            ha c[i][j+1] > c[i+1][j] akkor c[i][j] = c[i][j+1]
            különben c[i][j] = c[i+1][j]
            vége ha
        vége ha
    vége minden
vége minden
kiírás "A leghosszabb közös részsorozat hossza:", c[0][0]

// tömbbeli elemek kiertékelése: a közös részsorozat meghatározása 
i = 0
j = 0
amig i < n és j < m végezd
    ha a[i] == b[j] akkor
        kiírás a[i]
        i = i + 1
        j = j + 1
    különben
        ha c[i][j] == c[i][j+1] akkor j = j + 1
        különben i = i + 1
        vége ha
    vége ha
vége amig

példa1:
a = {3,6,12,4,5,8,13,7,10};
b = {1,2,3,4,6,7,8,12,13};
kimenet:
c =
4 4 4 3 3 2 2 2 1 0
3 3 3 3 3 2 2 2 1 0
3 3 3 3 2 2 2 2 1 0
3 3 3 3 2 2 2 1 1 0
2 2 2 2 2 2 2 1 1 0
2 2 2 2 2 2 2 1 1 0
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

a leghosszabb közös részsorozat hossza: 4
a részsorozat: {3, 6, 12, 13}