Динамичко програмирање - оптимизација

Увод

Динамичко програмирање је моћна техника за конструкцију алгоритама која се користи за решавање различитих група проблема. Као и подели па владај и динамичко програмирање је подскуп индуктивно-рекурзивне технике за конструкцију алгоритама. Полазни проблем делимо на подпроблеме, рекурзивно их решавамо и затим решења подпроблема обједињујемо у решење полазног проблема.

Да бисмо могли да применимо динамичко програмирање, полазни проблем мора да испуњава два услова:

1. Преклапање подпроблема - Приликом поделе полазног проблема на подпроблема, исти подпроблеми се појављују више пута. Прецизније, решење једног подпроблема зависи од решења других подпроблема или има утицај на њих.
2. Оптимална подструктура - Оптимално решење проблема сачињено је од оптималних решења његових подпроблема на сваком нивоу.

Кључно својство динамичког програмирања као технике за конструкцију алгоритама јесте избегавање вишеструког решавања идентичних подпроблема. Уместо тога, сваки подпроблем решавамо тачно једном и памтимо његово решење. Када током решавања полазног проблема или његових подпроблема поново наиђемо на већ решени подпроблем, нећемо га решавати изнова, већ ћемо искористити од раније познато решење. Дакле. кључна идеја динамичког програмирања је паметно трошење меморије да бисмо уштедели време. У пракси, динамичким програмирањем се експоненцијална решења најчешће спуштају на полиномијална.

На крају, потребно је нагласити разлике између подели-па-владај и динамичког програмирања:

• Подели па владај користимо када проблем можемо да поделимо на независне подпроблеме, тј. решавање једног подпроблема не зависи од, нити утиче на, решења других подпроблема. Подели па владај се ослања на принцип смањи за фактор, чиме се наивни кваратни алгоритми своде на логлинеарне. У случају да постоји преклапање подпроблема, подели па владај се не сме користити. Такође, подели па владај води ка неефикасним алгоритмима ако је подела на подпроблеме тривијална, тј. ако се своди на смањи за један. Кључна идеја је независно решавање подпроблема и комбиновање њихових решења у решење полазног проблема.
• Динамичко програмирање користимо када проблем можемо да поделимо на подпроблеме који се преклапају, тј. када решење једног подпроблема зависи од решења других подпроблема и када проблем испуњава својство оптималне подструктуре. За разлику од подели па владај, примена динамичког програмирања зависи само од проблема који се решава и не зависи од начина на који се проблем дели на подпроблема. Кључна идеја је избегавање вишеструког решавања идентичних подпроблема, тако што ћемо решења једном решених подпроблема сачувати и касније их само користити када год наиђемо на већ решени подпроблем.

Динамичким програмирањем се могу решити две класе проблема:

1. Проблеми пребројавања - Најчешће се ради о проблемима у којима је потребно пребројати на колико начина се неки задатак може решити. На пример, одредити број комбинација, број растављања броја на збирове, на колико начина се може вратити кусур итд.
2. Оптимизациони проблеми - Потребно је одредити максимално или минимално решење које испуњава дати скуп ограничења. На пример, одређивање максималне вредности предмета који се могу спаковати у ранац, одређивање минималног броја трансформација потребних да се једна реч пребаци у другу итд.

Треба приметити да се динамичко програмирање у свом основном облику фокусира само на добијање нумеричког решење, али не и на то како се до решења долази. Реконструкција решења је посебан проблем који даје одговор на питање како се до траженог нумеричког решења долази. У пракси се током извршавања алгоритма најчешће памте неке додатне информације које ће тек након целокупног решавања проблема, тј. одређивања нумеричког решења, бити коришћене за реконструкцију и одређивања начина на који се то нумеричко решење постиже.

Развијање алгоритма динамичким програмирањем има 4 фазе:

1. Индуктивно-рекурзивна конструкција решења - Решење проблема је потребно описати рекурентном релацијом. Приликом дефинисања рекурентне релације користимо све оне праксе дефинисане у опису индуктивно-рекурзивне технике за конструкцију алгоритама. Најчешће, директна имплементација рекурзивног алгоритма који прати индуктивно-рекурзивну конструкцију води ка решењу експоненцијалне временске сложености, што је неприхватљиво у пракси.
2. Мемоизација - Потребно је увести помоћну структуру података у којој ћемо памтити решења подпроблема. Други назив за овај корак је динамичко програмирање на ниже, јер током решавања крећемо од проблема величине $n$ и низом рекурзивних позива га постепено сводимо на базни случај. Чим решимо подпроблем, његово решење памтимо у помоћној структури података. Сваки следећи пут када наиђемо на тај исти подпроблем, само ћемо то познато решење прочитати, без поновног решавања. Оваквим поступком се алгоритам експоненцијалне сложености из корака 1 преводи у алгоритам полиномијалне сложености. Мемоизација је рекурзивни поступак и као основну ману има додатну меморијску сложеност због великог броја рекурзивних позива.
3. Елиминација рекурзије - Проблем можемо да решимо и итеративно. Потребно је да кренемо од основног случаја и систематски да изградимо решење читавог проблема. Решавање проблема се своди на попуњавање помоћне структуре података од мањих ка већим подпроблемима. Други назив за решавање проблема на овај начин је динамичко програмирање на више.
4. Меморијска оптимизација - Приликом решавања проблема одоздо на горе, тј. динамичким програмирањем на више, често нам за решавање текућег подпроблема нису потребна решења свих мањих подпроблема већ само неколико њих. У том случају, сва непотребна решења можемо да одбацимо и да их не чувамо. Тиме се може постићи незанемарљива уштеда у потрошњи меморије.
5. Реконструкција решења - Реконструкција решења није основни део алгоритма добијеним динамичким програмирањем. Да бисмо реконструисали решење, често је потребно да током попуњавања структуре података у кораку 3 чувамо додатне информације којима ћемо кодирати на који начин смо до тог решења дошли. У пракси се најчешће одлучујемо или за меморијску оптимизацију или за реконструкцију решења, јер није могуће постићи обе ствари истовремено.

Свему овоме претходи провера да ли проблем који се решава поседује оптималну подструктуру и да ли се подпроблеми преклапају. Ако проблем не испуњава ова два услова, динамичко програмирање се не може применити.

Напомена: У свим решењима бавићемо се искључиво алгоритмима, док учитавање и штампање резултата препуштамо читаоцу за вежбу.

Задатак 1

Едит-растојање између две ниске се дефинише у терминима операција уметања, брисања и измена слова прве речи којима се може добити друга реч. Свака од ове три операције има своју цену. Дефинисати програм који израчунава најмању цену операција којима се од прве ниске може добити друга. На пример, ако је цена сваке операције јединична, тада се ниска zdravo може претворити у bravo! најефикасније операцијом измене слова $z$ у $b$, брисања слова $d$ и уметања карактера $!$.

Улаз: Са стандардног улаза се учитавају две ниске дужине највише $100$ карактера, а затим цене операције уметања, брисања и измене (природни бројеви од $1$ до $10$, сваки у посебном реду).

Излаз: На стандардни излаз исписати тражену вредност едит-растојања.

Решење

Изведимо прво индуктивно-рекурзивну конструкцију.

• Ако је прва ниска празна, најефикаснији начин да се од ње добије друга ниска је да се уметне један по један карактер друге ниске, тако да је минимална цена једнака производу цене операције уметања и броја карактера друге ниске.
• Ако је друга ниска празна, најефикаснији начин да се од прве ниске добије празна је да се један по један њен карактер избрише, тако да је минимална цена једнака производу цене операције брисања и броја карактера прве ниске.
• Индуктивна хипотеза ће бити да умемо да решимо проблем за било која два префикса прве и друге ниске. Ако су последња слова прве и друге ниске једнака, онда је потребно претворити префикс без последњег слова прве ниске у префикс без последњег слова друге ниске. Ако нису, онда имамо три могућности:
  • Једна је да изменимо један од та два карактера у онај други и онда да, као у претходном случају, преведемо префиксе без последњих карактера један у други.
  • Друга могућност је да обришемо последњи карактер прве ниске и пробамо да претворимо тако њен добијени префикс у другу ниску.
  • Трећа могућност је да прву ниску трансформишемо у префикс друге ниске без последњег карактера и да затим додамо последњи карактер друге ниске.

На основу овога лако можемо дефинисати рекурзивну функцију која израчунава едит-растојање. Да нам се ниске не би мењале током рекурзије (што може бити споро), ефикасније је да ниске прослеђујемо у неизмењеном облику и да само прослеђујемо бројеве карактера њихових префикса који се тренутно разматрају.

static int edit_rastorajnje(string s, string t, int n, int m, 
        int cenaUmetanja, int cenaBrisanja, int cenaIzmene)
{
    // проверавамо основне случајеве
    if (n == 0)
        return m*cenaUmetanja;
    if (m == 0)
        return n*cenaBrisanja;
    // ако су последња слова иста, онда је цена једнака пребацивању
    // префикса прве речи у префикс друге речи
    if (s[n-1] == t[m-1])
        return edit_rastojanje(s, t, n-1, m-1, cenaUmetanja, cenaBrisanja, cenaIzmene);
    // ако последња слова нису иста, онда имамо три могућности
    // 1. бришемо последњи карактер прве речи и њен префикс преводимо у другу ниску
    int c1 = cenaBrisanja + edit_rastojanje(s, t, n-1, m, cenaUmetanja, cenaBrisanja, cenaIzmene);
    // 2. прву реч преводимо у префикс друге речи и затим умећемо последњи карактер друге речи
    int c2 = cenaUmetanja + edit_rastojanje(s, t, n, m-1, cenaUmetanja, cenaBrisanja, cenaIzmene);
    // 3. префикс прве речи преводимо у префикс друге речи и затим последње слово прве мењамо у 
    // последње слово друге речи
    int c1 = cenaIzmene + edit_rastojanje(s, t, n-1, m-1, cenaUmetanja, cenaBrisanja, cenaIzmene);
    // решење је операција најмање цене
    return Math.Min(c1, Math.Min(c2, c3));
}
static int edit_rastojanje(string s, string t, int cenaUmetanja, int cenaBrisanja, int cenaIzmene)
{
    return edit_rastojanje(s, t, s.Length, t.Length, cenaUmetanja, cenaBrisanja, cenaIzmene);
}

Приказано решење се лако мемоизује. Решење зависи од два параметра, па нам као помоћна структура треба матрица. Мемоизовано решење је у наставку:

static int edit_rastorajnje(string s, string t, int n, int m, 
        int cenaUmetanja, int cenaBrisanja, int cenaIzmene, int[,] memo)
{
    // ако је проблем већ решен, само вратимо познато решење
    if (memo[n, m] > 0)
        return memo[n,m];
    // проверавамо основне случајеве
    if (n == 0)
        return memo[n,m] = m*cenaUmetanja;
    if (m == 0)
        return memo[n,m] = n*cenaBrisanja;
    // ако су последња слова иста, онда је цена једнака пребацивању
    // префикса прве речи у префикс друге речи
    if (s[n-1] == t[m-1])
        return memo[n,m] = edit_rastojanje(s, t, n-1, m-1, cenaUmetanja, cenaBrisanja, cenaIzmene);
    // ако последња слова нису иста, онда имамо три могућности
    // 1. бришемо последњи карактер прве речи и њен префикс преводимо у другу ниску
    int c1 = cenaBrisanja + edit_rastojanje(s, t, n-1, m, cenaUmetanja, cenaBrisanja, cenaIzmene);
    // 2. прву реч преводимо у префикс друге речи и затим умећемо последњи карактер друге речи
    int c2 = cenaUmetanja + edit_rastojanje(s, t, n, m-1, cenaUmetanja, cenaBrisanja, cenaIzmene);
    // 3. префикс прве речи преводимо у префикс друге речи и затим последње слово прве мењамо у 
    // последње слово друге речи
    int c3 = cenaIzmene + edit_rastojanje(s, t, n-1, m-1, cenaUmetanja, cenaBrisanja, cenaIzmene);
    // решење је операција најмање цене
    return memo[n,m] = Math.Min(c1, Math.Min(c2, c3));
}
static int edit_rastojanje(string s, string t, int cenaUmetanja, int cenaBrisanja, int cenaIzmene)
{
    // помоћна структура у којој чувамо решења подпроблема
    int[,] memo = new int[s.Length+1, t.Length+1];
    // решеавамо проблем рекурзивно
    return edit_rastojanje(s, t, s.Length, t.Length, cenaUmetanja, cenaBrisanja, cenaIzmene, memo);
}

Решење директном рекурзијом је, наравно, неефикасно због преклапајућих рекурзивних позива. Алгоритам динамичког програмирања за овај проблем познат је под именом Вагнер-Фишеров алгоритам. Резултате за префиксе дужине $i$ и $j$ памтићемо у матрици на пољу $(i, j)$. Дакле, ако су дужине ниски $n$ и m$ , потребна нам је матрица димензије $(n + 1) \times (m + 1)$, а коначан резултат ће се налазити на месту $(n, m)$. У наставку ћемо приказати решење помоћу динамичког програмирања навише. Ако матрицу попуњавамо врсту по врсту, слева надесно, приликом израчунавања елемента на позицији $(i, j)$, биће израчунати сви елементи матрице од којег он зависи (а то су $(i − 1, j − 1)$, $(i − 1, j)$ и $(i, j − 1)$).

static int edit_rastojanje(string s, string t, int cenaUmetanja, int cenaBrisanja, int cenaIzmene)
{
    // помоћна структура у којој чувамо решења подпроблема
    int[,] memo = new int[s.Length+1, t.Length+1];
    // иницијализација основних случајева
    memo[0,0] = 0;
    for (int i = 0; i <= s.Length; i++)
        memo[i,0] = i* cenaBrisanja;
    for (int j = 0; k <= t.Length; j++)
        memo[0,j] = j * cenaUmetanja;
    // попуњавамо унутрашњост матрице
    for (int i = 1; i <= s.Length; i++)
    {
        for (int j = 1; j <= t.Length; j++)
        {
            //  ако су последња слова иста, онда гледамо префикс
            if (s[i-1] == t[j-1])
            {
                memo[i,j] = memo[i-1,j-1];
            }
            // ако нису, узимамо најмањи од три описана случаја
            else {
                int c1 = cenaBrisanja + memo[i-1,j];
                int c2 = cenaUmetanja + memo[i,j-1];
                int c3 = cenaIzmene + memo[i-1, j-1];
                memo[n,m] = Math.Min(c1, Math.Min(c2, c3));
            }
        }
    }
    // решеавамо проблем рекурзивно
    return memo[n,m];
}

Пошто елементи текућег реда зависе само од претходног, можемо извршити меморијску оптимизацију и истовремено чувати само један ред. Током ажурирања елемента на позицији $j$ његов део на позицијама строго мањим од $j$ ће чувати елементе текућег реда $i$, део од позиције $j$ надаље ће чувати елементе претходног реда $i − 1$. Променљива prethodni ће чувати вредност са поља $(i − 1, j − 1)$, а променљива tekuci ће чувати вредност са поља $(i − 1, j)$.

static int edit_rastojanje(string s, string t, int cenaUmetanja, int cenaBrisanja, int cenaIzmene)
{
    // помоћна структура у којој чувамо решења подпроблема
    int[] memo = new int[t.Length+1];
    // иницијализација основних случајева
    memo[0] = 0;
    for (int j = 0; k <= t.Length; j++)
        memo[j] = j * cenaUmetanja;
    // попуњавамо унутрашњост матрице
    for (int i = 1; i <= s.Length; i++)
    {
        int prethodni = memo[0];
        memo[0] = i*cenaBrisanja;
        for (int j = 1; j <= t.Length; j++)
        {
            int tekuci = memo[j];
            //  ако су последња слова иста, онда гледамо префикс
            if (s[i-1] == t[j-1])
            {
                memo[j] = prethodni;
            }
            // ако нису, узимамо најмањи од три описана случаја
            else {
                int c1 = cenaBrisanja + tekuci;
                int c2 = cenaUmetanja + memo[j-1];
                int c3 = cenaIzmene + prethodni;
                memo[n,m] = Math.Min(c1, Math.Min(c2, c3));
            }
            prethodni = tekuci;
        }
    }
    // решеавамо проблем рекурзивно
    return memo[j];
}

Задатак 2

У познатој продавници технике се организује наградна игра са следећим правилима:

• Сваки учесник ће добити ранац чија је носивост $W$.
• У наградној игри учествује $n$ различитих артикала.
• За сваки артикал позната је његова вредност $c_i$ и његова маса $w_i$.
• Сваки учесник може да изабере највише један артикал од сваке врсте.
• Задатак је изабрати артикле тако да не пређу дозвољену носивост ранца.
• Победник је такмичар који у ранцу буде имао највећу могућу вредност артикала.

Перица је препознао да се у наградној игри заправо ради о добро познатом проблему комбинаторне оптимизације који се назива 0-1 проблем ранца и замолио нас је да напишемо програм који ће му помоћи да победи у наградној игри.

Улаз: У првој линији стандардног улаза се учитава природан број који представља носивост ранца $W$. У следећој линији се учитава природан број $n$ који представља број артикала који учествују у наградној игри. У следећих $n$ линија учитавају се по два природна броја раздвојена једним размаком који редом представљајју вредност $c_i$ и масу $w_i$ $i$-тог артикла.

Излаз: На стандардни излаз исписати максималну вредност артикала која се може наћи у ранцу, као и скуп артикала који дају ту максималну вредност.

Решење

Имајући у виду опис проблема, једноставно је дефинисати рекурентну релацију која описује проблем. Очигледно је да за сваки предмет $i$ са масом $\omega_i$ и вредности $c_i$ имамо две опције:

• Предмет не додајемо у ранац - Вредност ранца остаје једнака као за претходних $i-1$ предмета са истим преосталим капацитетом.
• Предмет додајемо у ранац ако можемо - Ако је $\omega_i \le W$, додајемо вредност $c_i$ на максимуалну вредност ранца коју смо добили са $i-1$ предметом и смањеним капацитетм.

Нека је са $f(n,W)$ означена максимална вредност у ранцу капацитета $W$ са датих $n$ предмета познатих маса $\omega_i$ и вредности $c_i$. У том случају, рекурентна релација ће бити:

$$f(n, W) = \begin{aligned} \begin{cases} 0, & \text{ за } n = 0 \lor W = 0 \\ f(n - 1, W), & \text{ за } \omega_i > W \\ \max (f(n - 1, W), c_n + f(n - 1, W - \omega_n )), & \text{ иначе } \end{cases} \end{aligned}$$

Рекурзивна имплементација решења директно следи из индуктивно-рекурзивног описа решења:

static int ranac(int W, int[] mase, int[] cene, int n)
{
    // провера основног случаја
    if (n == 0 || W == 0)
        return 0;
    // одређујемо максимум без текућег предмета (искључи)
    int max = ranac(W, mase, cene, n - 1);
    // ако се текући предмет може додати у ранац
    if (mase[n-1] <= W)
    {
        // одређујемо решење са текућим предметом у ранцу (укључи)
        int r = cene[n-1] + ranac(W - mase[n-1], mase, cene, n - 1);
        // решење је максимум ова два случаја
        max = Math.Max(max, r);
    }
    // враћамо решење
    return max;
}
static int ranac(int W, int[] mase, int[] cene)
{
    return ranac(W, mase, cene, mase.Length);
}

Очигледно је да приказано решење има преклапање подпроблема. Да бисмо проблем могли да решавамо динамичким програмирањем морамо да покажемо да проблем поседује својство оптималне подструктуре. Оптимална подструктура подразумева да је оптимално решење састављено од оптималних решења подпроблема. Ово можемо лако да покажемо свођењем на контрадикцију.

Ако оптимално решење није састављено од оптималних решења подпроблема, то би значило да за макар један подпроблем можемо да изаберемо артикле у ранцу на другачији начин којим бисмо добили решење подпроблема које је веће вредности. Када то решење подпроблема укључимо у решење полазног проблема, добићемо решење које је веће вредности од раније одређеног оптималног решења. Дакле, постојање решења бољег од оптималног је немогуће, па смо извели контрадикцију.

С обзиром да наш проблем испуњава оба услова, можемо га решити динамичким програмирањем. Решење проблема зависи од два параметра, $W$ и $n$, па као помоћну структуру можемо да користимо матрицу. Мемоизовано решење је у наставку:

static int ranac(int W, int[] mase, int[] cene, int n)
{
    // ако смо већ решили проблем, само враћамо познато решење
    if (memo[n,W] >= 0)
        return memo[n,W];
    // провера основног случаја
    if (n == 0 || W == 0)
        return memo[n,W] = 0;
    // одређујемо максимум без текућег предмета (искључи)
    int max = ranac(W, mase, cene, n - 1);
    // ако се текући предмет може додати у ранац
    if (mase[n-1] <= W)
    {
        // одређујемо решење са текућим предметом у ранцу (укључи)
        int r = cene[n-1] + ranac(W - mase[n-1], mase, cene, n - 1);
        // решење је максимум ова два случаја
        max = Math.Max(max, r);
    }
    // враћамо решење
    return memo[n,W] = max;
}
static int ranac(int W, int[] mase, int[] cene)
{
    // креирамо и иницијализујемо помоћну структуру података
    int[,] memo = new int[mase.Length + 1, W + 1];
    for (int i = 0; i <= mase.Length; i++)
        for (int j = 0; j <= W; j++)
            mase[i,j] = -1;
    // рекурзивно решавамо проблем
    return ranac(W, mase, cene, cene.Length, memo);
}

Елиминација рекурзије се такође може врло лако одредити. Потребно је само уочити да вредност у текућем пољу матрице зависи од вредности директно изнад тог поља и од неке већ раније израчунате вредности у истом реду. Потребно је да матрицу попуњавамо ред по ред.

static int ranac(int W, int[] mase, int[] cene)
{
    // креирамо и иницијализујемо помоћну структуру података
    int[,] memo = new int[mase.Length + 1, W + 1];
    // базни случај (n = 0)
    for (int ј = 0; ј <= W; j++)
        memo[0,j] = 0;
    // попуњавамо матрицу
    for (int i = 1; i <= mase.Length; i++)
    {
        // базни случај (W = 0)
        memo[i, 0] = 0;
        // остатак попуњавамо по формули
        for (int j = 1; j <= W; j++)
        {
            memo[i,j] = memo[i-1,j];
            if (mase[i - 1] <= j)
                memo[i,j] = Math.Max(memo[i,j], cene[i-1] + memo[i-1, j - mase[i-1]]);
        }
    }
    // враћамо резултат
    return memo[n,W];
}

Меморијска оптимизација се такође може врло лако одрадити. Потребно је само да уочимо да текућа вредност зависи само од вредности директно изнад и вредности лево од себе. Због тога је довољно да чувамо само један ред матрице, а не целу матрицу. Десно од текуће позиције ће нам бити вредности из тренутне итерације, а лево од текуће позиције ће нам бити вредности из претходне итерације. Због тога ћемо ред попуњавати здесна на лево.

static int ranac(int W, int[] mase, int[] cene)
{
    // креирамо и иницијализујемо помоћну структуру података
    int[,] memo = new int[W + 1];
    // базни случај (n = 0)
    for (int ј = 0; ј <= W; j++)
        memo[j] = 0;
    // попуњавамо матрицу
    for (int i = 1; i <= mase.Length; i++)
    {
        // остатак попуњавамо по формули
        for (int j = W; j >= 0; j--)
        {
            if (mase[i - 1] <= j)
                memo[j] = Math.Max(memo[j], cene[i-1] + memo[j - mase[i-1]]);
        }
    }
    // враћамо резултат
    return memo[W];
}

Задатак 3

Напиши програм који израчунава дужину највећег заједничког подниза две ниске. Подниз чине карактери ниске који не морају бити узастопни, али се јављају у истом редоследу као у оригиналној ниски. На пример за ниске $abacbc$ и $babbca$ најдужа заједничка подниска је $babc$.

Улаз: Две линије стандардног улаза садрже две ниске које се састоје од малих слова енглеске азбуке и дугачке су највише $1000$ карактера.

Излаз: На стандардни излаз исписати само тражену дужину.

Решење

Ако је било која од две ниске празна, тада је једини њен подниз празан, па је дужина најдужег заједничког подниза једнака нули. Ако су обе ниске непразне, тада можемо упоредити њихова последња слова. Ако су она једнака, могу бити укључена у најдужи заједнички подниз и проблем се рекурзивно своди на проналажење најдужег заједничког подниза њихових префикса. У супротном, није могуће да оба последња слова буду укључена у заједнички подниз. Зато разматрамо најдужи заједнички подниз прве ниске и префикса друге ниске без њеног последњег слова и заједнички подниз друге ниске и префикса прве ниске без њеног последњег слова. Дужи од два подниза биће најдужи заједнички подниз те две ниске. Нагласимо и да није неопходно разматрати најдужи заједнички подниз два префикса, јер се проширивањем неког од два префикса за последње слово не може добити подниз који би био краћи. Дакле, пошто рекурзија тече по префиксима ниски, једини променљиви параметри током рекурзије могу бити дужине тих префикса.

Ако са $f(m,n)$ означимо дужину најдужег заједничког подниза префикса ниске $a$ дужине $m$ и префикса ниске $b$ дужине $n$, тада важи следећа рекурентна веза:

$$f(m,n) = \begin{aligned} \begin{cases} 0, & \text{ за } m = 0 \lor n = 0 \\ f(m-1,n-1) + 1, & \text{ за } a_{m-1} = b_{n-1} \\ \max (f(m-1, n), f(m, n-1)), & \text{ за } a_{m-1} \ne b_{n-1} \end{cases} \end{aligned}$$

static int najduzi_zajednicki_podniz(string s, string t, int m, int n)
{
    // провера основног случаја
    if (m == 0 || n == 0)
        return 0;
    // рекурзивно одређујемо решења када се последња слова не узимају у обзир
    int r1 = najduzi_zajednicki_podniz(s, t, m-1, n);
    int r2 = najduzi_zajednicki_podniz(s, t, m, n-1);
    // решење је већи од два броја
    int r = Math.Max(r1, r2);
    // ако су последња слова иста, онда морамо да испитамо и префиксе
    if (s[m-1] == t[n-1])
        r = Math.Max(r, najduzi_zajednicki_podniz(s, t, m-1, n-1));
    // враћамо резултат
    return r;
}
static int najduzi_zajednicki_podniz(strin s, string t)
{
    return najduzi_zajednicki_podniz(s, t, s.Length, t.Length);
}

У директном рекурзивном решењу има много преклапајућих рекурзивних позива. Стога је ефикасност могуће поправити техником динамичког програмирања. Један могући приступ је да употребимо мемоизацију. Вредност дужине најдужег подниза за сваки пар дужина префикса можемо памтити у матрици.

static int najduzi_zajednicki_podniz(string s, string t, int m, int n, int[,] memo)
{
    //  ако смо већ решавали проблем, не решавамо га поново
    if (memo[m,n] >= 0)
        return memo[n,m];
    // провера основног случаја
    if (m == 0 || n == 0)
        return memo[n,m] = 0;
    // рекурзивно одређујемо решења када се последња слова не узимају у обзир
    int r1 = najduzi_zajednicki_podniz(s, t, m-1, n, memo);
    int r2 = najduzi_zajednicki_podniz(s, t, m, n-1, memo);
    // решење је већи од два броја
    int r = Math.Max(r1, r2);
    // ако су последња слова иста, онда морамо да испитамо и префиксе
    if (s[m-1] == t[n-1])
        r = Math.Max(r, najduzi_zajednicki_podniz(s, t, m-1, n-1, memo));
    // враћамо резултат
    return memo[n,m] = r;
}
static int najduzi_zajednicki_podniz(strin s, string t)
{
    // креирамо и иницијализујемо помоћну структуру података
    int[,] memo = new int[s.Length + 1, t.Length + 1];
    for (int i = 0; i <= s.Length; i++)
        for (int j = 0; j <= t.Length; j++)
            mase[i,j] = -1;
    // рекурзивно решавамо проблем
    return najduzi_zajednicki_podniz(s, t, s.Length, t.Length, memo);
}

Проблем преклaпајућих рекурзивних позива се може решити ако се употреби динамичко програмирање навише. Дужине најдужих поднизова префикса можемо чувати у матрици. Елемент матрице на позицији $(i, j)$ зависи само од елемената на позицијама $(i − 1, j)$, $(i, j − 1)$ и $(i − 1, j − 1)$, тако да матрицу пожемо да попуњавамо било врсту по врсту, било колону по колону. Итеративно решење које попуњава матрицу ред по ред је у наставку:

static int najduzi_zajednicki_podniz(string s, string t)
{
    // памтимо дужине стрингова
    int m = s.Length, n = st.Length;
    // креирамо помоћну структуру података (основни случај је нула)
    int[,] memo = new int[m + 1, n + 1];
    // попуњавамо унутрашњост матрице
    for (int i = 1; i <= n1; i++)
    {
        for (int j = 1; j <= n2; j++)
        {
            // решење је максимум вредности без последњих карактера
            memo[i, j] = Math.Max(memo[i, j-1], memo[i-1, j]);
            // ако су последњи карактери исти, онда и њих упоређујемо
            if (s[i-1] == t[j-1])
                memo[i, j] = Math.Max(memo[i, j], memo[i-1, j-1] + 1);
        }
    }
    // враћамо решење
    return memo[m, n];
}

Можемо приметити да се приликом попуњавања матрице врсту по врсту садржај сваке наредне врсте попуњава само на основу претходне врсте. Стога није потребно истовремено памтити целу матрицу, већ је довољно памтити само једну, текућу врсту. Ажурирање врсте морамо вршити с лева надесно, јер сваки елемент у текућој врсти зависи од елемента који му претходи у тој врсти. Приметимо да нам је у неком тренутку потребно да знамо претходни елемент текуће врсте, а понекад претходни елемент претходне врсте, тако да приликом ажурирања врсте морамо да у помоћној променљивој памтимо стару вредност претходног елемента врсте (јер се ажурирањем претходног елемента његова стара вредност губи, а она нам може затребати у случају да су одговарајући карактери у нискама једнаки).

static int najduzi_zajednicki_podniz(string s, string t)
{
    // памтимо дужине стрингова
    int m = s.Length, n = st.Length;
    // креирамо помоћну структуру података (основни случај је нула)
    int[] memo = new int[n + 1];
    // попуњавамо унутрашњост матрице
    for (int i = 1; i <= n1; i++)
    {
        // памтимо вредност из претходне врсте
        int prethodni = memo[0];
        // попуњавамо врсту слева на десно
        for (int j = 1; j <= n2; j++)
        {
            // памтимо текућу вредност из врсте
            int tekuci = memo[j];
            // ако су слова иста, увећавамо дужину префикса
            if (s[i-1] == t[j-1])
                memo[j] = prethodni + 1;
            // иначе бирамо дужи од заједничких поднизова префикса 
            else
                memo[j] = Math.Max(memo[j-1]. memo[j]);
            // текућа вредност је претходна за наредни елемент врсте
            prethodni = tekuci;
        }
    }
    // враћамо решење
    return memo[n];
}

Задатак 4

Дефинисати функцију која одређује дужину најдуже заједничке подниске (узастопних карактера) две дате ниске. На пример, за ниске $ababc$ и $babbca$ најдужа заједничка подниска је $ab$.

Улаз: Свака од две линије стандардног улаза садржи ниску састављену од малих слова енглеске абецеде, дужине највише $1000$ карактера.

Излаз: На стандардни излаз исписати дужину најдуже заједничке подниске.

Решење

Као и до сада, први корак у решавању задатка је индуктивно-рекурзивна конструкција решења. Нека су дате две ниске $s$ и $t$. Нека је $m$ дужина ниске $s$ и нека је $n$ дужина ниске $t$. Тада можемо да закључимо следеће:

1. Базни случај - Ако је било која ниска празна, тј. ако је дужина било које ниске $0$, тада ће дужина најдуже заједничке подниске бити $0$.
2. Индуктивна хипотеза - Претпоставићемо да знамо дужину најдужег заједничког суфикса за све префиксе ниски $s$ и $t$ који су краћи од тренутних врености индекса $m$ и $n$. Прецизније, за сваку могућу вредност $m$ и $n$ знамо дужину најдуже заједничке ниске која се на тој позицији завршава.
3. Индуктивни корак (конструкција) - Према индуктивној хипотези познате су нам дужине најдужих заједничких суфикса за све префиксе ниски, па треба да проверимо само да ли текући карактери проширују постојећи подстринг или не. Имамо две могућности:
   • Карактери су једнаки, тј. $s_{m-1} = t_{n-1}$. У овом случају проширујемо заједничку подниску која се завршава на претходној позицији, тј. дужина заједничког суфикса ће бити за један већа.
   • Карактери се разликују. тј. $s_{m-1} \ne t_{n-1}$. У овом случају се прекида континуитет, па заједнички суфикс који се завршава не овом месту више не постоји, тј. дужина заједничког суфикса ће бити нула.

Укупно решење проблема ће бити највећа дужина суфикса коју нађемо уз помоћ свих рекурзивних позива.

Из описа решења проблема, лако добијамо следећу рекурентну релацију за израчунавање најдужег заједничког подстринга за конкретне позиције $m$ и $n$:

$$f(m,n) = \begin{aligned} \begin{cases} 0, & \text{ за } m = 0 \lor n = 0 \\ f(m-1,n-1) + 1, & \text{ за } s_{m-1} == t_{n-1} \\ 0, & \text{ за } s_{m-1} \ne t_{n-1} \end{cases} \end{aligned}$$

Укупно решење проблема $F(m,n)$ биће највећа вредност функције $f(m,n)$, за све могуће вредности $m$ и $n$. Да бисмо одредили решење, потребно је да упоредимо дужину текућег најдужег суфикса $f(m,n)$ са резултатима добијеним скраћивањем једне $F(m-1,n)$ или друге ниске $F(m, n-1)$. Прецизније, комплетно решење проблема се може описати следећом рекурентном релацијом

$$F(m,n) = \begin{aligned} \max \begin{cases} f(m,n), & \\ F(m-1,n) + 1, & \\ F(m, n-1). & \end{cases} \end{aligned}$$

Проблем можемо решити директном имплементацијом рекурентне релације уз одређивање максимума по свим позивима.

static int sufiks(string s, string t, int m, int n)
{
    // базни случај (било која од ниски је дужине нула)
    // случај када се последњи карактери разликују
    if (m == 0 || n == 0 || s[m-1] != t[n-1])
        return 0;
    // ако су последњи карактери једнаки, тада је дужина за један већа
    // од најдужег суфикса који се завршава на претходној позицији
    return 1 + sufiks(s, t, m-1, n-1);
}
static int najduzi_zajednicki_podstring(string s, string t, int m, int n)
{
    // провера базног случаја
    if (m == 0 || t == 0)
        return 0;
    // одређујемо дужину најдужег заједничко суфикса на позицијама m, n
    int duzina = sufiks(s, t, m, n);
    // одређујемо дужину најдужег заједничког суфикса након скраћивања прве ниске
    int duzina_s1 = najduzi_zajednicki_podstring(s, t, m-1, n);
    // одређујемо дужину најдужег заједничког суфикса након скраћивања друге ниске
    int duzina_t1 = najduzi_zajednicki_podstring(s,t,m,n-1);
    // резултат је највећи од ове три вредности
    return Math.Max(duzina, Math.Max(duzina, duzina_s1, duzina_t1));
}
static int najduzi_zajednicki_podstring(string s, string t)
{
    // рекурзивно решавамо задатак
    return najduzi_zajednicki_podstring(s, t, s.Length, t.Length);
}

Као и до сада, лако можемо извршити мемоизацију. С обзиром да наше решење зависи од два параметра, користићемо матрицу за памћење резултат подпроблема. Треба приметити да је наше решења симултана рекурзија две функције $f(m,n)$ и $F(m,n)$. Због тога су нам у кораку мемоизације потребне две матрице. Једну ћемо да користимо за мемоизовање вредности $F(m,n)$, а другу за мемоизовање вредности $f(m,n)$,

static int sufiks(string s, string t, int m, int n, int[,] memo_f)
{
    // ако смо проблем већ решили, само враћамо резултат
    if (memo_f[m,n] != -1)
        return memo_f[m,n];
    // базни случај (било која од ниски је дужине нула)
    // случај када се последњи карактери разликују
    if (m == 0 || n == 0 || s[m-1] != t[n-1])
        return memo_f[m,n] = 0;
    // ако су последњи карактери једнаки, тада је дужина за један већа
    // од најдужег суфикса који се завршава на претходној позицији
    return memo_f[m,n] = 1 + sufiks(s, t, m-1, n-1);
}
static int najduzi_zajednicki_podstring(string s, string t, int m, int n, int[,] memo_F, int[,] memo_f)
{
    // ако смо проблем већ решили, само враћамо резултат
    if (memo_F[m,n] != -1)
        return memo_F[m,n];
    // провера базног случаја
    if (m == 0 || t == 0)
        return memo_F[m,n] = 0;
    // одређујемо дужину најдужег заједничко суфикса на позицијама m, n
    int duzina = sufiks(s, t, m, n, memo_f);
    // одређујемо дужину најдужег заједничког суфикса након скраћивања прве ниске
    int duzina_s1 = najduzi_zajednicki_podstring(s, t, m-1, n, memo_F, memo_f);
    // одређујемо дужину најдужег заједничког суфикса након скраћивања друге ниске
    int duzina_t1 = najduzi_zajednicki_podstring(s,t,m,n-1, memo_F, memo_f);
    // резултат је највећи од ове три вредности
    return memo_F[m,n] = Math.Max(duzina, Math.Max(duzina, duzina_s1, duzina_t1));
}
static int najduzi_zajednicki_podstring(string s, string t)
{
    // креирамо и иницијализујемо матрицу
    int[,] memo_f = new int[s.Length + 1, t.Length + 1];
    int[,] memo_F = new int[s.Length + 1, t.Length + 1];
    for (int i = 0; i <= s.Length; i++) 
    {
        for (int j = 0; i <= t.Length; t++) 
        {
            memo_f[i,j] = -1;
            memo_F[i,j] = -1;
        }
    }
    // рекурзивно решавамо задатак
    return najduzi_zajednicki_podstring(s, t, s.Length, t.Length, memo_F, memo_f);
}

Задатак се може решити и паметнијом организацијом меморије. Уместо две матрице можемо да користимо само једну. Приметимо да матрицу memo_F користимо само за чување максималних вредности, док за стварно рачунање и чување резултат користимо матрицу memo_f. Нама треба само глобални максимум, а то можемо лако да постигнемо користећи само једну променљиву уместо матрице memo_F.

static int najduzi_zajednicki_podstring(string s, string t, int m, int n, int[,] memo_f, ref int max)
{
    // ако смо проблем већ решили, само враћамо резултат
    if (memo_ф[i,j] != -1)
        return memo_f[i,j];
    // провера базног случаја
    if (m == 0 || t == 0)
        return memo_f[i,j] = 0;
    // одређујемо дужину најдужег заједничког суфикса након скраћивања прве ниске
    najduzi_zajednicki_podstring(s, t, m-1, n, memo_f, ref max);
    // одређујемо дужину најдужег заједничког суфикса након скраћивања друге ниске
    najduzi_zajednicki_podstring(s,t,m,n-1, memo_f, ref max);
    // провера текућег суфикса
    if (s[m-1] == t[n-1])
        memo_f[m,n] = 1 + najduzi_zajednicki_podstring(s, t, m-1, n-1, memo_f, ref max);
    else 
        memo_f[m,n] = 0;
    // ажурирање максимума по потреби
    if (memo[m,n] > max)
        max = memo[m,n];
    // резултат је највећи од ове три вредности
    return memo_f[m,n];
}
static int najduzi_zajednicki_podstring(string s, string t)
{
    // креирамо и иницијализујемо матрицу
    int[,] memo_f = new int[s.Length + 1, t.Length + 1];
    for (int i = 0; i <= s.Length; i++) 
    {
        for (int j = 0; j <= t.Length; t++) 
        {
            memo_f[i,j] = -1;
        }
    }
    // максимум је на старту 0
    int max = 0;
    // рекурзивно решавамо задатак
    najduzi_zajednicki_podstring(s, t, s.Length, t.Length, memo_f, ref max);
    // враћамо резултат
    return max;
}

Рекурзија се може врло лако елиминисати из последњег решења. Потребно је да попунимо матрицу према описаном правилу и да током попуњавања истовремено рачунамо максималну вредност.

static int najduzi_zajednicki_podstring(string s, string t)
{
    // памтимо дужине стрингова
    int m = s.Length;
    int n = t.Length;
    // креирамо и иницијализујемо матрицу
    int[,] memo = new int[m + 1, n + 1];
    // максимум је на старту нула
    int maks = 0;
    // попуњавамо матрицу ред по ред
    for (int i = 1; i <= s.Length; i++) 
    {
        for (int j = 1; j <= t.Length; t++) 
        {
            // ако су карактери исти
            if (s[i-1] == t[j-1])
            {
                // примењујемо правило и ажурирамо макс по потреби
                memo[i, j] = 1 + memo[i-1,j-1];
                if (memo[i,j] > maks)
                    maks = memo[i,j];
            }
            else 
            {
                memo[i,j] = 0;
            }
        }
    }
    // враћамо резултат
    return maks;
}

На крају, могуће је и извршити меморијску оптимизацију итеративног решења. Лако се може уочити да текући ред зависи само од реда директно изнад њега, па бисмо наивно могли да сведемо меморијску потрошњу на само два реда, уместо да користимо целу матрицу. Међутим, потрошња меморије се може смањити на само један ред. Потребно је да уочимо да наше текуће решење зависи само од решења која се налазе лево од њега, па можемо да применимо добро познати трик попуњавања реда уназад, тј. здесна на лево.

static int najduzi_zajednicki_podstring(string s, string t)
{
    // оптимизација, увек ћемо дужу ниску прогласири за s,
    // краћу за t
    if (s.Length < t.Length)
    {
        string tmp = s;
        s = t;
        t = tmp;
    }
    // памтимо дужине стрингова
    int m = s.Length;
    int n = t.Length;
    // креирамо и иницијализујемо матрицу
    int[] memo = new int[n + 1];
    // максимум је на старту нула
    int maks = 0;
    // попуњавамо матрицу ред по ред
    for (int i = 1; i <= s.Length; i++) 
    {
        for (int j = n; j >= 1; j--) 
        {
            // ако су карактери исти
            if (s[i-1] == t[j-1])
            {
                // примењујемо правило и ажурирамо макс по потреби
                memo[j] = 1 + memo[j-1];
                if (memo[j] > maks)
                    maks = memo[j];
            }
            else 
            {
                memo[j] = 0;
            }
        }
    }
    // враћамо резултат
    return maks;
}

Задатак 5

Написати програм који одређује најдужи строго растући подниз (не обавезно узастопних елемената) унутар датог низа.

Улаз: Са стандардног улаза се учитава број елемената низа $n$ $(1 \leq n \leq 50000)$, а затим елементи низа (цели бројеви, сваки у посебном реду).

Излаз: На стандардни излаз исписати дужину најдужег растућег подниза.

Решење

Приказаћемо два решења заснована на динамичком програмирању, која су различите ефикасности.

У првој групи решења разматраћемо позицију по позицију у низу и одредићемо најдужи растући подниз чији је последњи елемент на свакој од њих. Приликом одређивања дужине најдужег растућег подниза који се завршава на позицији $i \ge 0$, претпоставићемо да за сваку претходну позицију (ако их има) умемо да одредимо дужину најдужег растућег подниза који се на њој завршава. Низ који се завршава на позицији $i$ сигурно садржи елемент $a_i$, а може продужити све оне низове који се завршавају на некој позицији $0 \le j < i$ ако је $a_j < a_i$. Да би низ који се завршава на позицији $j$ био што дужи, његов префикс који се завршава на позицији $j$ мора бити што дужи (а дужине тих низова можемо одредити рекурзивно). Зато од свих низова који се завршавају на позицијама $j$ таквим да је $a_j < a_i$ одређујемо најдужи и продужавамо га елементом $a_i$ (ако таквих елемената нема, тада је најдужи низ који се завршава на позицији $a_i$ једночлан).

static int najduzi_rastuci_podniz(int[] niz, int i)
{
    // најдужи растући подниз је сам елемент на позицији i
    int maksI = 1;
    // испитујемо сваки елемент из префикса
    for (int j = 0; j < i; j++)
    {
        // ако је елемент из префикса мањи од елемента
        // на позицији i, можемо га укључити у растући подниз
        if (a[j] < a[i])
        {
            // па рекурзивно одређујемо најдужи растући подниз који
            // се завршава на позицији j 
            int maksJ = najduzi_rastuci_podniz(niz, j);
            // по потреби ажурирамо максимум
            if (maksJ + 1 > maksI)
                maksI = maksJ + 1;
        }
    }
    // враћамо резултат
    return maksI;
}
static int najduzi_rastuci_podniz(int[] niz)
{
    // на старту максимум је нула
    int maks = 0;
    // за сваку позицију у низу
    for (int i = 0; i < niz.Length; i++)
    {
        // одређујемо најдужи растући подниз који се на тој позицији завршава
        int maksI = najduzi_rastuci_podniz(niz, i);
        // по потреби ажурирамо максимум
        if (maksI > maks)
            maks = maksI;
    }
    // враћамо резултат
    return maks;
}

Када се претходна рекурзивна веза директно имплементира, долази до понављања идентичних рекурзивних позива, што доводи до велике неефикасности. Проблем решавамо динамичким програмирањем. За мемоизацију довољно је да памтимо низ дужина најдужих растућих низова који се завршавају на свакој позицији у низу. Пошто су све те дужине веће или једнаке од $1$ (сваки елемент сам за себе чини растући низ), низ у који памтимо решења можемо иницијализовати нулама (што значи да је тражена дужина још непозната).

static int najduzi_rastuci_podniz(int[] niz, int i, int[] memo)
{
    // ако смо проблем већ решили, само враћамо решење
    if (memo[i] != 0)
        return memo[i];
    // најдужи растући подниз је сам елемент на позицији i
    int maksI = 1;
    // испитујемо сваки елемент из префикса
    for (int j = 0; j < i; j++)
    {
        // ако је елемент из префикса мањи од елемента
        // на позицији i, можемо га укључити у растући подниз
        if (a[j] < a[i])
        {
            // па рекурзивно одређујемо најдужи растући подниз који
            // се завршава на позицији j 
            int maksJ = najduzi_rastuci_podniz(niz, j, memo);
            // по потреби ажурирамо максимум
            if (maksJ + 1 > maksI)
                maksI = maksJ + 1;
        }
    }
    // враћамо резултат
    return memo[i] = maksI;
}
static int najduzi_rastuci_podniz(int[] niz)
{
    // помоћна структура у којој памтимо решења подпроблема
    int[] memo = new int[niz.Length + 1];
    // на старту максимум је нула
    int maks = 0;
    // за сваку позицију у низу
    for (int i = 0; i < niz.Length; i++)
    {
        // одређујемо најдужи растући подниз који се на тој позицији завршава
        int maksI = najduzi_rastuci_podniz(niz, i, memo);
        // по потреби ажурирамо максимум
        if (maksI > maks)
            maks = maksI;
    }
    // враћамо резултат
    return maks;
}

Једноставно можемо формулисати и динамичко програмирање навише, тако што низ попуњавамо слева надесно. Након попуњавања низа одређујемо његов максимум. Нагласимо да сваки наредни елемент низа потенцијално зависи од великог броја претходних тако да није могуће редуковати меморијску сложеност тиме што би се памтили само неки елементи низа (морамо увек знати дужине свих претходних елемената). Решење које се добија на овај начин је меморијске сложености $O(n)$ и временске сложености $O(n^2)$.

Прикажимо на примеру како ће се тај низ попуњавати.

$$\begin{aligned} i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \text{niz} & 3 & 2 & 6 & 9 & 5 & 4 & 3 & 7 & 8 & 2 \\ \text{memo} & 1 & 1 & 2 & 3 & 2 & 2 & 2 & 3 & 4 & 1 \end{aligned}$$

На пример, када израчунавамо елемент на позицији $5$ анализирамо низове који се завршавају елементима мањим од вредности $4$ која се налази на позицији $5$. То су вредности $3$ на позицији $0$ и $2$ на позицији $1$. У оба случаја максимална дужина подниза који се завршава на тој позицији је $1$, па се било који од тих низова продужава елементом $4$ и добија се растући низ дужине $2$.

Итеративно решење добијено динамичким програмирањем навише је у наставку:

static int najduzi_rastuci_podniz(int[] niz)
{
    // помоћна структура у којој памтимо решења подпроблема
    int[] memo = new int[niz.Length + 1];
    // за сваку позицију у низу
    for (int i = 0; i < niz.Length; i++)
    {
        // одређујемо најдужи подниз који се ту завршава
        memo[i] = 1;
        // проверавамо све елементе из префикса
        for (int j = 0; j < i; j++)
        {
            // ако је елемент и префикса мањи од елемента на позицији i
            // ажурирамо дужину најдужег растућег подниза
            if (a[i] > a[j] && memo[j] + 1 > memo[i])
                memo[i] = memo[j] + 1;
        }
    }
    // одређујемо дужину најдужег растућег подниза
    int max = memo[0];
    for (int i = 1; i < n; i++>)
    {
        if (memo[i] > max)
            max = memo[i];
    }
    // враћамо резултат
    return max;
}

Претходно решење је сложености $O(n^2)$, али изменом индуктивно-рекурзивне конструкције можемо добити и много ефикасније решење. Кључна идеја је да претпоставимо да уз дужину $d_{\text{max}}$ најдужег растућег подниза до сада обрађеног дела низа можемо за сваку дужину подниза $1 d d_{} $ да одредимо најмањи елемент којим се завршава неки растући подниз дужине $d$. Приметимо да низ тих вредности увек строго растући (ако постоји строго растући низ дужине $d$ који се завршава неким елементом $a_i$, тада се његов префикс дужине $d − 1$ мора завршавати неким елементом који је строго мањи од елемента $a_i$).

Низ обрађујемо елемент по елемент. Размотримо један пример (колоне табеле су означене дужинама низа), а елементи низа који се обрађују су написани десно.

$$\begin{aligned} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & | & &\\ - & - & - & - & - & - & - & - & - & - & | & &\\ 3 & - & - & - & - & - & - & - & - & - & | & 3 &\\ 2 & - & - & - & - & - & - & - & - & - & | & 2 &\\ 2 & 6 & - & - & - & - & - & - & - & - & | & 6 &\\ 2 & 6 & 9 & - & - & - & - & - & - & - & | & 9 &\\ 2 & 5 & 9 & - & - & - & - & - & - & - & | & 5 &\\ 2 & 4 & 9 & - & - & - & - & - & - & - & | & 4 &\\ 2 & 3 & 9 & - & - & - & - & - & - & - & | & 3 &\\ 2 & 3 & 7 & - & - & - & - & - & - & - & | & 7 &\\ 2 & 3 & 7 & - & - & - & - & - & - & - & | & 2 &\\ 2 & 3 & 7 & 8 & - & - & - & - & - & - & | & 8 & \end{aligned}$$

Ако се досадашњи најдужи подниз завршавао елементом који је мањи од текућег, онда смо нашли подниз који је дужи за један и најмањи елемент на крају тог подниза је текући. То се у примеру дешава приликом обраде елемента $3$, елемента $6$, елемента $9$ и елемента $8$.

Размотримо ситуацију у којој обрађујемо елемент $5$. До тада смо видели елементе $3$, $2$, $6$ и $9$. Елемент $2$ на првој позицији у табели означава да је најмањи елемент којим се може завршити једночлани растући низ једнак $2$. Елемент $6$ на другој позицији у табели означава да је најмањи елемент којим се може завршити двочлани растући низ једнак $6$ (у питању је низ $2$ $6$ или низ $3$ $6$). Елемент $9$ на трећој позицији у табели означава да је најмањи елемент којим се може завршити трочлани растући низ једнак $9$ (у питању је низ $2$ $6$ $9$ или $3$ $6$ $9$). Пошто је $5$ мањи од $9$ ниједан од ових трочланих низова није могуће проширити елементом $5$, па је четворочланих растућих низова нема. Поставља се питање да ли се можда трочлани низови могу завршити елементом $5$, но ни то није могуће. Наиме, пошто је у табели двочланим низовима придружена вредност $6$, то значи да се сви двочлани растући низови завршавају бар са $6$, па није могуће $9$ заменити са $5$. Са друге стране, пошто је $5$ веће од $2$, завршни елемент двочланих низова $6$ је могуће заменити са $5$ и тиме добити мању завршну вредност двочланих низова (то су у овом случају низови $3$ $5$ и $2$ $5$). Дакле, у табели вредност $6$ треба заменити вредношћу $5$. Вредност $2$ лево од $6$ нема смисла заменити са $5$, јер би се тиме завршна вредност једночланих низова увећала, а ми у табели памтимо најмање завршне вредности.

На основу анализе овог примера можемо да закључимо да је приликом анализе сваког текућег елемента потребно пронаћи прву позицију $d$ у табели на којој се налази елемент који је већи или једнак од текућег и на позицију $d$ уместо тога уписати текући елемент. Ако су сви елементи мањи од текућег (ако је $d = d_{\text{max}}$ ), онда се текући елемент додаје на крај низа (и у том случају заправо радимо исто - уписујемо елемент на позицију $d$). Остали елементи у табели остају непромењени. Заиста на свим позицијама у табели лево од позиције $d$ уписани су елементи строго мањи од текућег и њиховом заменом са текућим се не би смањила вредност завршног елемената тих низова. За елементе десно од позиције $d$, иако су већи од текућег, ажурирање није могуће. У свим низовима дужине $d′ > d$ неки префикс се морао завршавати елементом на позицији $d$ или елементом већим од њега, а пошто је он био већи или једнак од текућег, заменом последњег елемента текућим не бисмо добили више растући низ.

Кључни добитак настаје када се примети да, пошто су елементи у табели сортирани, позицију првог елемента који је већи или једнак од текућег можемо остварити бинарном претрагом. Отуда следи ефикасна имплементација (у низу memo вредност најмањег завршног елемента за низове дужине $d$ памтимо на позицији $d − 1$). Временска сложеност такве имплементације је $O(n \cdot \log (n))$, док је меморијска сложеност $O(n)$.

static int najduzi_rastuci_podniz(int[] niz)
{
    int n = niz.Length;
    int[] memo = new int[n+1];
    int max = 0;
    for (int i = 0; i < n; i++)
    {
        int p = Array.BinarySearch(memo, 0, max, niz[i]);
        if (p < 0)
            p = ~p;
        memo[p] = niz[i];
        if (p + 1 > max)
            max = p + 1;
    }
    return max;
}

Задатак 6

Дате су вредности $n$ врста новчића. Написати програм који одређује минималан број новчића потребних за исплату датог износа $S$, при чему се може користити и више новчића исте врсте и сваке врсте новчића има произвољно много. Вредности новчића и износ за исплату дати су у истој валути.

Улаз: Прва линија стандардног улаза задржи природан број $S$ $(S \leq 1000)$. Друга линија садржи природан број $n$ $(n \leq 100)$, у следећих $n$ линија налазе се природни бројеви који представљају вредности за сваку врсту новчића, свака вредност у посебној линији.

Излаз: На стандардном излазу приказати у једној линији минималан број новчића потребан ѕа исплату из- носа $S$.

Решење

Задатак можемо лако решити анализом последњег новчића. Износ $0$ се може наплатити са $0$ новчића. У супротном, ако је низ расположивих новчића празан, износ није могуће наплатити. У супротном испитујемо могућност да је у износ укључен новчић последње врсте. Ако није, покушавамо да наплатимо износ без коришћења последње врсте новчића, тј. са префиксом низа новчића без последњег елемента. Ако јесте, тада износ мора бити већи или једнак од новчића последње врсте и тада преостали износ покушавамо да наплатимо поново коришћењем свих врста новчића. Ако се са $f(n,s)$ обележи најмањи број новчића да се наплати износ $s$ помоћу новчића који припадају префиксу дужине $n$ полазног низа, тада важи следећа рекурентна релација:

$$f(n,s) = \begin{aligned} \begin{cases} 0, & \text{ за } s = 0 \\ +\infty, & \text{ за } n = 0, s > 0 \\ f(n-1, s), & \text{ за } s < v_{n-1} \\ \min (f(n-1, s), 1 + f(n, s - v_{n-1})) 0, & \text{ за } s \ge v_{n-1} \end{cases} \end{aligned}$$

На основу овога је веома једноставно дефинисати рекурзивну функцију која израчунава тражени најмањи број новчића.

static int najmanje_novcica(int[] niz, int n, int s)
{
    // провера основних случајева
    if (s == 0)
        return 0;
    if (n == 0)
        return int.MaxValue;
    // прво разматрамо најмањи број новчића без последњег (искључи)
    int br = najmanje_novcica(niz, n-1, s);
    // ако можемо да употребимо последњи новчић
    if (s >= niz[n-1])
        // укључујемо га у разматрање и по потреби ажурирамо минимум
        br = Math.Min(br, najmanje_novcica(niz, n, s - niz[n-1]) + 1);
    // враћамо резултат
    return br;
}
static int najmanje_novcica(int[] niz, int s)
{
    // проблем решавамо рекурзивно полазећи од последњег новчића
    return najmanje_novcica(niz, niz.Length, s);
}

Јасно је да у претходној функцији може доћи до понављања истих рекурзивних позива, што се може решити техником динамичког програмирања. Пошто функција има два променљива параметра, могуће је употребити матрицу за мемоизацију.

static int najmanje_novcica(int[] niz, int n, int s, int[,] memo)
{
    // ако смо већ решавали проблем, одмах враћамо решење
    if (memo[n,s] != -1)
        return memo[n,s];
    // провера основних случајева
    if (s == 0)
        return memo[n,s] = 0;
    if (n == 0)
        return memo[n,s] = int.MaxValue;
    // прво разматрамо најмањи број новчића без последњег (искључи)
    int br = najmanje_novcica(niz, n-1, s, memo);
    // ако можемо да употребимо последњи новчић
    if (s >= niz[n-1])
        // укључујемо га у разматрање и по потреби ажурирамо минимум
        br = Math.Min(br, najmanje_novcica(niz, n, s - niz[n-1], memo) + 1);
    // враћамо резултат
    return memo[n,s] = br;
}
static int najmanje_novcica(int[] niz, int s)
{
    // помоћна структура података у којој чувамо решења подпроблема
    int[,] memo = new int[niz.Length + 1, s + 1];
    for (int i = 0; i <= niz.Length; i++)
        for (int j = 0; j <= s; j++)
            memo[i,j] = -1;
    // проблем решавамо рекурзивно полазећи од последњег новчића
    return najmanje_novcica(niz, niz.Length, s, memo);
}

Приликом динамичког програмирања навише, матрицу можемо попуњавати врсту по врсту и тако смањити меморијску сложеност. Из рекурентне релације се лако може уочити да текућа вредност у матрици зависи само до вредности директно изнад ње и вредности лево од ње. Због тога не морамо да чувамо целу матрицу, већ је довољно да чувамо само један њен ред. Временска сложеност овог решења је $O(s \cdot n)$, где је $s$ износ, а $n$ број врста новића, док је меморијска сложеност $O(s)$.

static int najmanje_novcica(int[] niz, int s)
{
    // помоћна структура података у којој чувамо решења подпроблема
    int[] memo = new int[s + 1];
    // базни случај
    memo[0] = 0;
    for (int j = 1; j <= s; j++)
            memo[j] = int.MaxValue;
    //  укључујемо једну по једну врсту новчића
    for (int i = 1; i <= n; i++)
    {
        // ажурирамо вредности свих износа
        for (int j = 0; j <= s; j++)
        {
            // ако је могуће укључити новчић
            if (j >= niz[i-1])
                // ажурирамо минимум ако је то потребно
                memo[j] = Math.Min(memo[j], memo[j - niz[i-1]] + 1);
        }
    }
    // проблем решавамо рекурзивно полазећи од последњег новчића
    return memo[s];
}

Друго решење задатка може се добити анализом свих могућности за последњи новчић. То може бити било који новчић који је мањи од текућег износа који треба наплатити, након чега се преостали износ и даље наплаћује помоћу свих могућих новчића. Ако са $f(s)$ обележимо најмањи број новчића потребних да се наплати износ $s$, при чему се могу користити сви расположиви новчићи, добијамо следећу рекурентну везу:

$$f(s) = \begin{aligned} \begin{cases} 0, & \text{ за } s = 0 \\ \min{v_i <= s} (1 + f(s - v_i)), & \text{ за } s > 0 \end{cases} \end{aligned}$$

Ако је износ позитиван, али мањи од свих новчића које имамо на располагању тада је минимум једнак $+\infty$. И у овом случају веома једноставно можемо дефинисати рекурзивну функцију.

static int najmanje_novcica(int[] niz, int n, int s)
{
    // провера основних случајева
    if (s == 0)
        return 0;
    // на почетку претпостављамо да износ није могуће наплатити
    int br = int.MaxValue;
    // разматрамо све могућности за последњи новчић
    for (int i = 0; i < n; i++)
    {
        // ако новчић можемо да укључимо у збир
        if (niz[i] <= s)
            // рекурзивно одређујемо број новчића потребних за наплату
            // преосталог износа након укључивања новчића
            br = Math.Min(br, najmanje_novcica(niz, n, s - niz[i]) + 1);
    }
    // враћамо резултат
    return br;
}
static int najmanje_novcica(int[] niz, int s)
{
    // проблем решавамо рекурзивно полазећи од последњег новчића
    return najmanje_novcica(niz, niz.Length, s);
}

Пошто долази до понављања истих рекурзивних позива потребно је да употребимо динамичко програмирање. Пошто је само један параметар променљив, за мемоизацију је довољно само да користимо низ.

static int najmanje_novcica(int[] niz, int n, int s, int[] memo)
{
    // ако смо подпроблем већ решавали, само враћамо решење
    if (memo[s] != 0)
        return memo[s];
    // провера основних случајева
    if (s == 0)
        return memo[s] = 0;
    //  на почетку претпостављамо да износ није могуће наплатити
    int br = int.MaxValue;
    // разматрамо све могућности за последњи новчић
    for (int i = 0; i < n; i++)
    {
        // ако новчић можемо да укључимо у збир
        if (niz[i] <= s)
            // рекурзивно одређујемо број новчића потребних за наплату
            // преосталог износа након укључивања новчића
            br = Math.Min(br, najmanje_novcica(niz, n, s - niz[i], memo) + 1);
    }
    
    // враћамо резултат
    return memo[s] = br;
}
static int najmanje_novcica(int[] niz, int s)
{
    // помоћна структура података у којој чувамо решења подпроблема
    int[] memo = new int[s+1];
    // проблем решавамо рекурзивно полазећи од последњег новчића
    return najmanje_novcica(niz, niz.Length, s, memo);
}

Рекурзију елинишемо тако што наш помоћни низ попуњавамо слева на десно.

static int najmanje_novcica(int[] niz, int s)
{
    // помоћна структура података у којој чувамо решења подпроблема
    int[] memo = new int[s+1];
    // базни случај
    memo[0] = 0;
    for (int j = 0; j <= s; j++)
    {
        // претпостављамо да износ није могуће наплатити 
        memo[j] = int.MaxValue;
        // разматрамо сваки новчић
        for (int i = 0; i < niz.Length; i++)
        {
            // укључујемо га у збир ако можемо
            if (niz[i] <= j)
                // ажурирамо решење подпроблема
                memo[j] = Math.Min(memo[j], memo[j-niz[i]] + 1);
        }
    }
    // враћамо резултат
    return memo[s];;
}

Задатак 7

Написати програм који одређује највећи збир неког сегмента (подниза узастопних елемената) датог низа.

Улаз: Са стандардног улаза се уноси број $n$ $(1 \leq n \leq 50 000)$, а затим $n$ целих бројева између $−10$ и $10$, сваки број у посебном реду.

Излаз: На стандардни излаз исписати тражени збир.

Решење

С обзиром на то да се суфикси првих $i$ елемената низа могу анализирати инкрементално (суфикси $i + 1$ елемената низа се добијају проширивањем суфикса $i$ елемената низа додатним елементом), проблем анализе свих сегмената је пожељно свести на проблем анализе суфикса. У овом конкретном проблему, можемо приметити да је максимални збир сегмента уједно и максимални збир суфикса који се завршава на позицији на којој се тај сегмент завршава. Стога се задатак може свести на то да се за сваку позицију у низу одреди максимални суфикс, а да се онда међу максималним суфиксима за сваку позицију пронађе онај који је глобално максимални.

Једини суфикс првих нула елемената низа је празан и његов збир је по дефиницији $0$. Сви суфикси првих $i + 1$ елемената низа, изузев празног суфикса добијају се додавањем елемента на позицији $i$ на крај неког суфикса првих $i$ елемената низа. Међу непразним суфиксима највећи збир има онај који је добијен додавањем последњег елемента управо на суфикс првих $i$ елемената низа који има максимални збир. Од њега једино може бити већи збир празног суфикса (и то када се након проширивања последњим елементом добије негативни збир). Ако вредности максималног збира суфикса памтимо у низу, тада низ лако попуњавамо на основу веза $S_0 = 0$ и $S_{i+1} = \max (S_i + a_i , 0)$, где је са $S_i$ обележена вредност максималног збира суфикса првих $$ елемената низа $a$.

На крају налазимо максимум низа $S_i$.

Прикажимо рад алгоритма на примеру низа $-2, 3, 2, -3, -3, -2, 4, 5, -8, 3$. У таблици попуњавамо вредности $S_i$.

$$\begin{aligned} & i & | & a_{i+1} & | & S_i & \\ & 0 & | & & | & 0 & \\ & 1 & | & -2 & | & 0 = \max (0 + (-2), 0) & \\ & 2 & | & \phantom{-}3 & | & 3 = \max (0 + 3, 0) & \\ & 3 & | & \phantom{-}2 & | & 5 = \max (3 + 2, 0) & \\ & 4 & | & -3 & | & 2 = \max (5 + (-3), 0) & \\ & 5 & | & -3 & | & 0 = \max (2 + (-3), 0) & \\ & 6 & | & -2 & | & 0 = \max (0 + (-2), 0) & \\ & 7 & | & \phantom{-}4 & | & 4 = \max (0 + 4, 0) & \\ & 8 & | & \phantom{-}5 & | & 9 = \max (4 + 5, 0) & \\ & 9 & | & -8 & | & 1 = \max (9 + (-8), 0) & \\ & 10 & | & \phantom{-}3 & | & 4 = \max (1 + 3, 0) & \\ \end{aligned}$$

Максимална вредност у колони $S_i$ је $9$.

Пошто користимо низ максималних збирова суфикса, меморијска сложеност је $O(n)$. Низ попуњавамо елемент по елемент, инкрементално, у једном пролазу за шта је довољно $n$ корака, а затим максимум налазимо у новом пролазу тј. у нових $n$ корака. Укупна сложеност је, дакле, линеарна тј. $O(n)$. Описани алгоритам нам одмах даје итеративно решење, па рекурзивна нећемо уопште разматрати.

static int maksimalni_zbir_segmenta(int[] niz)
{
    // низ у којем чувамо решења подпроблема
    int[] maxSufiks = new int[niz.Length+1];
    // основни случај
    maxSufiks[0] = 0;
    // попуњавамо решења према описаном поступку
    for (int i = 0; i < niz.Length; i++)
    {
        maxSufiks[i+1] = Math.Max(maxSufiks[i] + niz[i], 0);
    }
    // одређујемо дужину најдужег суфикса
    int max = maxSufiks[0];
    for (int i = 1; i <= niz.Length; i++)
    {
        if (maxSufiks[i] > max)
            max = maxSufiks[i];
    }
    // враћамо резултат
    return max;
}

Максималне вредности збирова суфикса не морамо да памтимо у низу, ако њихов максимум одређујемо истовремено са одређивањем вредности максималних збирова суфикса. Овај алгоритам познат је под именом Каданов алгоритам.

Један начин да се дође до тог алгоритма је следећи. Покушавамо да алгоритам заснујемо на индуктивној конструкцији.

• За празан низ, једини сегмент је празан и његов је збир нула (то је уједно највећи збир који се може добити).

• Сматрамо да умемо да решимо проблем за произвољан низ дужине $n$ и на основу тога покушавамо да решимо задатак за низ дужине $n + 1$ (полазни низ проширен једним додатним елементом).

• Сегмент највећег збира у проширеном низу се или цео садржи у полазном низу дужине $n$ или чини суфикс проширеног низа, тј. завршава се на последњој позицији (укључујући и могућност да је ту и празан сегмент). На основу индуктивне хипотезе знамо да израчунамо највећи збир сегмента низа дужине $n$ и потребно је да још одредимо максимални збир суфкса проширеног низа. Један начин да се то уради је да приликом сваког проширења низа изнова анализирамо све сегменте који се завршавају на текућој позицији, али чак иако то радимо инкрементално (кренувши од празног суфикса, па додајући уназад један по један елемент) највише што можемо добити је алгоритам квадратне сложености (пробајте да се уверите да је то заиста тако). Кључни увид је то да највећи збир суфикса који се завршава на текућој позицији можемо инкрементално израчунати знајући највећи збир суфикса низа пре проширења. Највећи збир неког непразног суфикса који се завршава на текућој позицији је збир текућег елемента низа и највећег збира неког суфикса који се завршава на претходној позицији. Од њега може бити повољнији само празан суфикс (и то само ако је претходни збир негативан).

Дакле, ако са $S_i$ обележимо максимални збир неког суфикса првих $i$ елемената низа, а са $M_i$ максимални збир неког сегмента прих $i$ елемената низа, важи да је $M_0 = S_0 = 0$, да је $S_{i+1} = \max (S_i + a_i, 0)$ и $M_{i+1} = \max (M_i , S_i+1)$.

Имплементацију можемо направити итеративним алгоритмом коме је инваријанта да у сваком кораку петље знамо ове две вредности (максимум сегмента и максимум суфикса).

Прикажимо рад алгоритма на примеру низа $-2, 3, 2, -3, -3, -2, 4, 5, -8, 3$. У таблици попуњавамо вредности $S_i$ и $M_i$.

$$\begin{aligned} & i & | & a_{i+1} & | & S_i & | & M_i & \\ & 0 & | & & | & 0 & | & 0 &\\ & 1 & | & -2 & | & 0 = \max (0 + (-2), 0) & | & 0 = \max(0,0) &\\ & 2 & | & \phantom{-}3 & | & 3 = \max (0 + 3, 0) & | & 3 = \max(0,3) &\\ & 3 & | & \phantom{-}2 & | & 5 = \max (3 + 2, 0) & | & 5 = \max(3,5) &\\ & 4 & | & -3 & | & 2 = \max (5 + (-3), 0) & | & 5 = \max(5,2) &\\ & 5 & | & -3 & | & 0 = \max (2 + (-3), 0) & | & 5 = \max(5,0) &\\ & 6 & | & -2 & | & 0 = \max (0 + (-2), 0) & | & 5 = \max(5,0) &\\ & 7 & | & \phantom{-}4 & | & 4 = \max (0 + 4, 0) & | & 5 = \max(5,4) &\\ & 8 & | & \phantom{-}5 & | & 9 = \max (4 + 5, 0) & | & 9 = \max(5,9) &\\ & 9 & | & -8 & | & 1 = \max (9 + (-8), 0) & | & 9 = \max(9,1) &\\ & 10 & | & \phantom{-}3 & | & 4 = \max (1 + 3, 0) & | & 9 = \max(9,4) &\\ \end{aligned}$$

Пошто елементе обрађујемо један по један и не памтимо их истовремено, меморијска сложеност је $O(1)$. Максимални збир сегмента и суфикса инкрементално израчунавамо једним проласком кроз задате елементе и временска сложеност је линеарна тј. $O(n)$.

static int maksimalni_zbir_segmenta(int[] niz)
{
    // иницијализујемо врендости на почетку рада алгоритма
    int maxSufiks = 0ч
    int max = 0;
    // пролазимо кроз низ елемент по елемент
    for (int i = 0; i < niz.Length; i++)
    {
        // увећавамо збир суфикса
        maxSufiks += niz[i];
        // ресетујемо га на нула ако постане негативан
        if (maxSufiks < 0)
            maxSufiks = 0;
        // ажурирамо максимални збир суфикса, ако треба
        if (max < maxSufiks)
            max = maxSufiksl
    }
    // враћамо резултат
    return max;
}

Задатак 8

Испред лифта познате носивости се налазе предмети познате масе. Напиши програм који одређује најмањи потребан број вожњи да би се сви предмети превезли.

Улаз: Са стандардног улаза се учитава број предмета $n$ ($1 \le n \le 20$), затим масе предмета (цели бројеви између $1$ и $50$) и на крају носивост лифта (цео број између $50$ и $120$).

Излаз: На стандардни излаз исписати тражени број вожњи.

Решење

Задатак решавамо индуктивно-рекурзивном конструкцијом. Ако се превози само један предмет тада се он превози сам, једном вожњом. Посматрамо скуп од $n > 1$ предмета. Сваки од њих може бити онај који је последњи убачен у лифт. За сваки предмет рекурзивно одређујемо најмањи број вожњи који је потребан да се превезу сви предмети без тог (имамо дакле $n$ подпроблема димензије $n − 1$). Остаје питање да ли се тај последњи предмет може убацити у неку од већ постојећих вожњи или је потребно превести га посебно. Да бисмо једноставно могли дати одговор на ово питање, морамо ојачати индуктивну хипотезу и уз минималан број вожњи за предмете без текућег, морамо бити у могућности и да за све оптималне вожње тих предмета одредимо и ону у којој је маса предмета у последњем лифту минимална (то је уједно најмања маса у било којој вожњи, јер ако се најмања могућа маса добија у некој вожњи пре последње, увек можемо пермутовати ту вожњу са последњом). Пошто претпостављамо да је тренутни предмет тај који последњи улази у лифт, онда он или допуњује последњи лифт у коме се већ возе неки предмети испред њега, или се вози сам, у посебној вожњи. Први случај се дешава ако тај последњи од предмета стаје у последњи, најмање оптерећен лифт (ако је збир његове масе и масе предмета који су већ у том последњем лифту мањи или једнак носивости лифта), а други, ако не стаје. Пошто је последњи предмет фиксиран и обавезно се налази у последњем лифту, можемо лако одредити и најмању могућу масу у последњем лифту. У првом случају та маса је једнака збиру масе предмета који су већ у последњем лифту и масе тог предмета, док је у другом случају та маса једнака само маси тог предмета. Анализирањем свих избора последњег предмета и проналажењем минималног броја вожњи за сваки од избора и минималне масе у последњем лифту за сваки фиксирани избор последњег предмета добијамо најмањи могући број вожњи за свих $n$ особа, као и најмању могућу масу у последњем лифту за тих $n$ особа, чиме је начињен индуктивни корак.

Као и до сада подскупове ћемо представљати помоћним низом нула и јединица. Јединица на позицији $i$ ће означавати да предмет $i$ припада подскупу. С обзиром да је број предмета мали, подскупови се могу кодирати и помоћу бит вектора чиме се може постићи меморијска уштеда.

Решење које директно прати описану рекурзивну коснтрукцију је у наставку:

static void najmanji_broj_voznji(int[] mase, int nosivost, int[] podskup, int n, 
                                    out int minVoznji, out int minPoslednjaMasa)
{
    //  ако је преостао само један предмет
    if (n == 1)
    {
        // можемо га превести у једној вожњи
        minVoznji = 1;
        // маса предмета је најмања маса
        minPoslednjaMasa = 0;
        for (int i = 0; i < mase.Length; i++)
        {
            if (podskup[i] == 1)
                minPoslednjaMasa = mase[i];
        }
    }
    // ако треба да превеземо више предмета
    else 
    {
        // претпосављамо да је минимални број вожњи једнак броју предмета
        minVoznji = mase.Length;
        // последњу тежину постављамо на бесконачно
        minPoslednjaMasa = nosivost;
        // пролазимо кроз преостале елементе
        for (int i = 0; i < mase.Length; i++)
        {
            // ако се предмет налази у подскупу
            if (podskup[i] == 1)
            {
                // oдређујемо решење без предмета i
                int minVoznjiI, minPoslednjaMasaI;
                podskup[i] = 0;
                najmanji_broj_voznji(mase, nosivost, podskup, n-1, out minVoznjiI, out minPoslednjaMasaI);
                // реконструишемо подскуп
                podskup[i] = 1;
                // ако i-ти предмет стаје у последњи лифт
                if (minPoslednjaMasaI + mase[i] <= nosivost)
                {
                    // додајемо га у последњи лифт
                    minPoslednjaMasaI += mase[i];
                }
                // ако i-ти предмет не може да стане у последњи лифт
                else {
                    /// увећавамо број вожњи
                    minVoznjiI++;
                    // ажурирамо масу последњег лифта, ако треба
                    if (mase[i] < minPoslednjaMasaI)
                        minPoslednjaMasaI = mase[i];
                }
                // ажурирамо глобални минимум, ако је то потребно
                if (minVoznjiI < minVoznji || 
                    (minVoznjiI == minVoznji && minPoslednjaMasaI < minPoslednjaMasa>))
                {
                    minVoznji = minVoznjiI;
                    minPoslednjaMasa = minPoslednjaMasaI;
                }
            }
        }
    }
}
static int najmanji_broj_voznji(int[] mase, int nosivost)
{
    // креирамо помоћне вредности
    int n = mase.Length;
    int podskup = new int[n];
    int minVoznji, minPoslednjaMasa;
    // рекурзивно решавамо проблем
    najmanji_broj_voznji(mase, nosivost, podskup, n, out minVoznji, out minPoslednjaMasa);
    // враћамо решење
    return minVoznji;
}

Пошто се у овако дефинисаној рекурзивној процедури рекурзивни позиви преклапају у имплементацији је неопходно применити технике динамичког програмирања. Једно решење је да се примени мемоизација. Имплементацију можемо мало поједноставити ако за излаз из рекурзије узмемо празан уместо једночланог скупа и кажемо да се он може превести једном вожњом у којем је маса последњег лифта једнака $0$. Параметар од којег зависи наш резултат је подскуп, па бисмо њиме морали да индексирамо структуру података којом вршимо мемоизацију. Подскупове смо представљали низом чији смо садржај мењали током рада програма. Коришћење низа као кључа у речнику, није могуће, јер се кључеви упоређују по референци, а не по садржају. Због тога, подскупове треба другачије да кодирамо. То ћемо најједноставније учинити употребом битова. Број предмета које треба да превеземо је мањи од 20, што значи да можемо да користимо један int и његових најнижих 20 битова за репрезентацију подскупа. Одавде закључујемо да се сви могући подскупови могу представити неозначеним бројевима (и то од $0$ до $2^{n − 1}$), за мемоизацију онда можемо употребити низ димензије $2^n$. С обзиром да је $n \le 20$, укупно ће нам бити потребно $\approx 10^6$ вредности, што можемо да упамтимо у низу. За сваки подскуп треба да знамо потребан број вожњи и масу последњег лифта.

Дакле, подскупове ћемо кодирати битовима унутар целог броја представљеног са $32$ бита, чиме смо сваки подскуп једнозначно придружили целом броју. Резултате ћемо чувати у посебном типу података Raspored у којем ћемо енкапсулирати број вожњи и тежину последњег лифта. Мемоизовано решење је у наставку:

// помоћни типо података за кодирање решења
class Raspored
{
    // поља класе
    public int BrojVoznji {get; set;}
    public int PoslednjaMasa {get; set;}
    // коснтруктор
    public Raspored(int bv, int pm)
    {
        BrojVoznji = bv;
        PoslednjaMasa = pm;
    }
    //  упоређивач
    public bool da_li_je_bolji(Raspored r)
    {
        return brojVoznji < r.BrojVoznji ||
            (brojVoznji == r.BrojVoznji && PoslednjaMasa < r.PoslednjaMasa);
    }
}
static Raspored najmanji_broj_voznji(int[] mase, int nosivost, uint podskup, 
                                        int n, Raspored[] memo)
{
    // ако смо већ решили проблем, само враћамо решење
    if (memo[podskup] != null && memo[podskup].brojVoznji != 0)
        return memo[podskup];
    //  аko је лифт празан
    if (n == 0)
    {
        // тада имамо само једну вожњу са масом 0
        return new Raspored(1, 0);
    }
    // ако треба да превеземо више предмета
    else 
    {
        // минимум иницијизујемо на највећи број
        Raspored min = new Raspored(mase.Length, nosivost);
        // сваки предмет може бити у последњем лифту
        for (int i = 0; i < mase.Length; i++)
        {
            // ако се предмет налази у подскупу
            if ((podskup & (1<<i)) != 0)
            {
                // oдређујемо решење без предмета i
                Raspored minI = najmanji_broj_voznji(mase, nosivost, podskup ^ (1 << i), n - 1, memo);
                // ако i-ти предмет стаје у последњи лифт
                if (minI.PoslednjaMasa + mase[i] <= nosivost)
                {
                    // додајемо га у последњи лифт
                    minI.PoslednjaMasa += mase[i];
                }
                // ако i-ти предмет не може да стане у последњи лифт
                else {
                    /// увећавамо број вожњи
                    minI.BrojVoznji++;
                    // mаса последњег лифта је једнака маси предмета који се разматра
                    minI.PoslednjaMasa = mase[i];
                }
                // ажурирамо глобални минимум, ако је то потребно
                if (minI.da_li_je_bolji(min))
                {
                    min = minI;
                }
            }
        }
        return memo[podskup] = min;
    }
}
static int najmanji_broj_voznji(int[] mase, int nosivost)
{
    // креирамо помоћне вредности
    int n = mase.Length;
    // подскупове кодирамо битовима
    uint podskup = (1u << n) - 1;
    // креирамо помоћну структуру података у којој чувамо 
    // решења подпроблема
    Raspored[] memo = new Raspored[1 << n];
    // враћамо решење
    return najmanji_broj_voznji(mase, nosivost, podskup, n, memo).BrojVoznji;
}

Задатак се може решити и динамичким програмирањем навише, при чему је тада потребно обратити пажњу на редослед обиласка подскупова тако да смо сигурни да су пре сваког скупа обрађени сви његови подскупови (један начин да то урадимо је да подскупове кодирамо неозначеним бројевима и да их обрађујемо у растућем редоследу).

Сложеност овог приступа једнака је $O(n \cdot 2^n)$ (број подскупова је $2^n$ и за сваки од њих се анализира сваки могући избор последњег предмета).

// помоћни типо података за кодирање решења
class Raspored
{
    // поља класе
    public int BrojVoznji {get; set;}
    public int PoslednjaMasa {get; set;}
    // коснтруктор
    public Raspored(int bv, int pm)
    {
        BrojVoznji = bv;
        PoslednjaMasa = pm;
    }
    //  упоређивач
    public bool da_li_je_bolji(Raspored r)
    {
        return brojVoznji < r.BrojVoznji ||
            (brojVoznji == r.BrojVoznji && PoslednjaMasa < r.PoslednjaMasa);
    }
}
static int najmanji_broj_voznji(int[] mase, int nosivost)
{
    // креирамо помоћне вредности
    int n = mase.Length;
    // креирамо помоћну структуру података у којој чувамо 
    // решења подпроблема
    Raspored[] memo = new Raspored[1 << n];
    // базни случај, празан подскуп
    memo[0] = new Raspored(1,0);
    // пролазимо кроз све подскупове
    for (uint i = 1; i < (1 << n); i++)
    {
        //  за текући подскуп претпостављамо да треба максималан број вожњи
        memo[i] = new Raspored(n + 1, 0);
        // разматрамо све предмете
        for (int j = 0; j < n; j++)
        {
            // ако подскуп садржи текући елемент
            if ((i & (1 << n)) != 0)
            {
                // рачунамо решење без тог елемента
                Raspored minI = memo[i ^ (1 << n)];
                // ако се предмет може укључити у раније познато решење
                if (minI.PoslednjaMasa + mase[j] <= nosivost)
                {
                    // само повећавамо масу у последњем лифту
                    minI.PoslednjaMasa += mase[j];
                }
                // иначе увећавамо број вожњи
                else 
                {
                    minI.BrojVoznji++;
                    minI.PoslednjaMasa = mase[j];
                }
                // проверавамо да ли смо нашли боље решење и 
                // ажурирамо минимум ако треба
                if (minI.da_li_je_bolji(memo[i]))
                    memo[i] = minI;
            }
        }
    }
    // враћамо решење
    return memo[(1 << n) - 1].brojVoznji;
}