Metoda programării dinamice

Metoda a fost dezvoltată de matematicianul american Richard Bellman, în anii 1950, ca metodă de optimizare a proceselor de decizie. În denumirea ei, cuvântul programare are sensul de planificare, nu de scriere a programelor.

Descrierea metodei

Metoda se folosește pentru problemele care au caracteristicile următoare:

Pentru o asemenea problemă, rezolvarea directă construiește toate soluțiile posibile și o păstrează pe cea mai bună. La problema rucsacului, de exemplu, se generează toate submulțimile celor n obiecte, adică 2ⁿ variante de încărcare, iar timpul de execuție crește exponențial. Programarea dinamică nu mai enumeră soluțiile: din soluțiile optime ale subproblemelor mici se obțin, prin relația de recurență, soluțiile optime ale subproblemelor mai mari.

Principiul optimalității

Rezolvarea unei probleme se poate privi ca un șir de decizii d1, d2, …, dn. Fiecare decizie trece problema dintr-o stare în alta, de la starea inițială S0, prin stările intermediare S1, …, Sn−1, până la starea finală Sn, din care se obține soluția.

Principiul se demonstrează, pentru fiecare problemă, prin reducere la absurd. Dacă una dintre subprobleme ar admite o soluție mai bună decât cea conținută în soluția optimă, înlocuirea ei ar produce o soluție mai bună pentru problema întreagă, ceea ce contrazice ipoteza.

După ordinea în care se stabilesc deciziile, metoda se aplică astfel:

Principiul optimalității conduce la o relație de recurență.

Etapele de rezolvare

1. Se demonstrează că problema are substructură optimă, de obicei prin reducere la absurd.
2. Se caracterizează structura soluției optime: în ce subprobleme se descompune problema și ce valoare se calculează pentru fiecare dintre ele.
3. Se definește recursiv valoarea soluției optime, printr-o relație de recurență, împreună cu valorile cazurilor de bază.
4. Se calculează valoarea soluției optime de jos în sus: întâi subproblemele de dimensiune minimă, apoi cele care se bazează pe ele, până la problema inițială. Valorile calculate se memorează într-un tabel.
5. Se construiește soluția optimă din informațiile memorate în tabel.

Când problema cere numai valoarea optimă, cum ar fi o lungime, un profit sau un număr de termeni, etapa a cincea nu mai este necesară.

Calculul relației de recurență

Relația de recurență se poate calcula de jos în sus sau de sus în jos:

Varianta de sus în jos, scrisă direct după relația de recurență, rezolvă o subproblemă de câte ori apare aceasta în descompunere, deci este ineficientă. Ea devine eficientă prin memoizare.

Memoizarea se aplică astfel:

• tabelul se inițializează cu o valoare care nu poate fi rezultatul niciunei subprobleme, de exemplu −1;
• la fiecare apel se verifică întâi tabelul: dacă subproblema a fost deja rezolvată, apelul întoarce valoarea memorată;
• altfel, apelul calculează valoarea, o memorează în tabel și abia apoi o întoarce.

Astfel fiecare subproblemă se rezolvă tot o singură dată, ca în varianta de jos în sus. Deosebirea este că se rezolvă numai subproblemele de care depinde efectiv problema inițială.

Aplicațiile din această lecție sunt scrise în amândouă variantele: iterativ, de jos în sus, și recursiv, cu memoizare.

Exemplu: termenii șirului lui Fibonacci

Șirul lui Fibonacci este definit prin f1 = f2 = 1 și fn = fn−1 + fn−2, pentru n > 2. Relația de recurență scrisă direct ca funcție recursivă este:

fib(n):
    dacă n ≤ 2 atunci
        returnează 1
    altfel
        returnează fib(n − 1) + fib(n − 2)
    sfdacă

Subproblemele nu sunt independente. Apelul fib(5) cere fib(4) și fib(3), iar fib(4) cere din nou fib(3). În total, fib(3) se calculează de două ori, iar fib(2) de trei ori. Numărul apelurilor pentru fib(n) este 2·fn − 1, deci crește exponențial: pentru n = 30 se execută 1 664 079 de apeluri.

Prin programare dinamică, fiecare termen se calculează o singură dată:

fibonacci(n):
    f[1] ← 1; f[2] ← 1
    pentru i ← 3, n execută
        f[i] ← f[i − 1] + f[i − 2]
    sfpentru
    returnează f[n]

// f[i] = 0 înseamnă că termenul i
// nu a fost încă calculat
fibonacci(i):
    dacă f[i] = 0 atunci
        dacă i ≤ 2 atunci
            f[i] ← 1
        altfel
            f[i] ← fibonacci(i − 1) + fibonacci(i − 2)
        sfdacă
    sfdacă
    returnează f[i]

long long f[91];

/* Termenii se calculeaza de jos in sus: fiecare
   se obtine din cei doi memorati inaintea lui. */
long long fibonacci(int n) {
    f[1] = 1;
    f[2] = 1;
    for (int i = 3; i <= n; i++)
        f[i] = f[i - 1] + f[i - 2];
    return f[n];
}

long long f[91];    // initial 0: termen necalculat

/* Termenul i se calculeaza o singura data; la
   apelurile urmatoare se intoarce valoarea memorata. */
long long fibonacci(int i) {
    if (f[i] == 0) {
        if (i <= 2)
            f[i] = 1;
        else
            f[i] = fibonacci(i - 1) + fibonacci(i - 2);
    }
    return f[i];
}

# Termenii se calculeaza de jos in sus: fiecare
# se obtine din cei doi memorati inaintea lui.
def fibonacci(n):
    f = [0] * (n + 1)
    f[1] = 1
    if n >= 2:
        f[2] = 1
    for i in range(3, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]

f = [0] * 91    # 0: termen necalculat


# Termenul i se calculeaza o singura data; la
# apelurile urmatoare se intoarce valoarea memorata.
def fibonacci(i):
    if f[i] == 0:
        if i <= 2:
            f[i] = 1
        else:
            f[i] = fibonacci(i - 1) + fibonacci(i - 2)
    return f[i]

Amândouă variantele efectuează n − 2 adunări, deci au ordinul de complexitate O(n). Termenul fi depinde numai de fi−1 și fi−2, așa că în varianta iterativă tabelul se poate înlocui cu două variabile, care rețin ultimii doi termeni calculați.

Exemplul are rol didactic: nu este o problemă de optimizare, dar arată pe un caz simplu ce câștig aduce memorarea soluțiilor subproblemelor.

Oportunitatea utilizării metodei

Metoda este oportună pentru problemele de optimizare cu substructură optimă la care celelalte metode nu dau un algoritm corect sau eficient:

• metoda greedy nu garantează soluția optimă — alegerea cea mai bună la un pas poate împiedica o soluție mai bună, cum se întâmplă la problema rucsacului în variantă discretă;
• metoda backtracking este prea lentă — ea găsește soluția optimă, dar enumeră toate soluțiile, deci timpul este exponențial;
• metoda divide et impera ar repeta calcule — subproblemele nu sunt independente, deci aceeași subproblemă s-ar rezolva de mai multe ori.

Folosirea ei aduce avantaje, dar are și limite:

Algoritmul metodei

Un algoritm de programare dinamică, scris de jos în sus, are forma generală următoare:

algoritm programareDinamica
    pentru fiecare subproblemă elementară s execută
        T[s] ← valoarea lui s, calculată direct       // cazurile de bază
    sfpentru
    pentru fiecare subproblemă s, în ordinea stabilită, execută
        T[s] ← valoarea optimă obținută din valorile
               subproblemelor de care depinde s, memorate în T
    sfpentru
    scrie valoarea problemei inițiale, memorată în T
    construiește soluția optimă pe baza valorilor din T
stop algoritm programareDinamica

Ordinea în care se completează tabelul se alege astfel încât, la calculul lui T[s], toate valorile de care depinde s să fie deja memorate. La subșirul crescător tabelul se completează de la ultimul termen spre primul, la rucsac și la subșirul comun linie cu linie.

Programul se organizează, de obicei, în subprogramele următoare:

• init — inițializează tabelul cu valorile cazurilor de bază;
• pDinamica — completează tabelul după relația de recurență;
• afiseaza — scrie valoarea optimă și construiește soluția.

Pentru construirea soluției optime, decizia luată la fiecare subproblemă:

• se memorează într-un tablou separat, de exemplu indicele termenului următor din subșir;
• sau se deduce din valorile tabelului, comparând valoarea unei subprobleme cu valorile subproblemelor din care putea proveni.

Complexitatea metodei

Timpul de execuție al unui algoritm de programare dinamică este produsul dintre numărul subproblemelor și timpul necesar pentru rezolvarea unei subprobleme, adică numărul variantelor comparate la calculul unei valori din tabel.

Rezolvarea prin enumerarea tuturor soluțiilor are, la aceleași probleme, ordin exponențial: un șir cu n termeni are 2ⁿ subșiruri, iar n obiecte formează 2ⁿ variante de încărcare a rucsacului.

Problemele rezolvate prin această metodă

• determinarea unui subșir crescător de lungime maximă;
• problema rucsacului în variantă discretă;
• determinarea unui subșir comun de lungime maximă;
• obținerea unei sume date din termeni distincți ai unui șir;
• suma maximă a numerelor de pe un drum într-un triunghi de numere;
• calculul combinărilor C(n, k) cu ajutorul triunghiului lui Pascal.

Primele trei sunt trecute anume în programa de examen, ca aplicații specifice ale metodei, și sunt scrise mai jos. A patra a fost dată la Titularizare 2023 și este rezolvată în secțiunea despre examen.

Subșirul crescător de lungime maximă

Enunțul problemei

Se consideră un șir a cu n numere întregi (n ≤ 100). Un subșir se obține din șirul dat prin eliminarea unor termeni, fără schimbarea ordinii celor rămași. Să se determine un subșir strict crescător de lungime maximă.

Date de intrare. Pe prima linie numărul n, pe a doua cele n numere, separate prin câte un spațiu.

Date de ieșire. Pe prima linie lungimea maximă, pe a doua termenii unui subșir strict crescător de această lungime.

Ideea de rezolvare

Subproblema i este determinarea celui mai lung subșir strict crescător care începe cu termenul a[i]. Lungimea lui se notează cu L[i].

Dacă acest subșir are cel puțin doi termeni, al doilea termen este un a[j], cu j > i și a[j] > a[i], iar restul subșirului este un subșir strict crescător care începe cu a[j]. Restul are lungimea maximă L[j]: dacă ar exista un subșir mai lung care începe cu a[j], atunci, pus după a[i], el ar da un subșir mai lung care începe cu a[i], ceea ce contrazice ipoteza. Problema are, așadar, substructură optimă.

De aici rezultă relația de recurență:

L[n] = 1
L[i] = 1 + max{ L[j] | i < j ≤ n și a[i] < a[j] },   pentru i < n
L[i] = 1,   dacă după a[i] nu urmează niciun termen mai mare

Subproblemele nu sunt independente: valoarea L[j] intră în calculul tuturor valorilor L[i] cu i < j și a[i] < a[j].

Fiecare L[i] folosește valori L[j] cu indici mai mari, deci tabelul se completează de la ultimul termen spre primul. Decizia pentru termenul i depinde de deciziile luate pentru termenii de după el, deci se aplică metoda înainte.

Pentru construirea soluției se memorează, în urm[i], indicele termenului care urmează după a[i] în subșirul optim, sau 0 dacă a[i] este ultimul termen. Subșirul căutat începe cu termenul a[k] pentru care L[k] este maxim, iar termenii următori se obțin din urm.

Exemplul pentru șirul 5 2 8 6 3 6 9 7

Valorile se calculează de la dreapta la stânga:

• L[8] = 1 și L[7] = 1, fiindcă după 7 nu mai urmează niciun termen, iar după 9 nu urmează niciun termen mai mare;
• pentru a[6] = 6 se pot continua subșirurile care încep cu 9 și cu 7, amândouă de lungime 1, deci L[6] = 2 și urm[6] = 7;
• pentru a[5] = 3 cea mai mare lungime dintre termenii mai mari care urmează este L[6] = 2, deci L[5] = 3 și urm[5] = 6;
• pentru a[2] = 2 toți termenii care urmează sunt mai mari, iar cea mai mare lungime este L[5] = 3, deci L[2] = 4 și urm[2] = 5.

Valoarea maximă din L este L[2] = 4. Subșirul începe cu a[2] = 2 și continuă cu termenii de pe pozițiile urm[2] = 5, urm[5] = 6 și urm[6] = 7: 2 3 6 9.

Șirul are și alte subșiruri strict crescătoare de lungime 4, de exemplu 2 3 6 7. Programul îl afișează pe primul găsit, fiindcă L[i] se modifică numai când se obține o lungime strict mai mare.

Programul

pDinamica():
    pentru i ← n, 1, −1 execută
        L[i] ← 1; urm[i] ← 0
        pentru j ← i + 1, n execută
            dacă a[i] < a[j] și L[j] + 1 > L[i] atunci
                L[i] ← L[j] + 1; urm[i] ← j
            sfdacă
        sfpentru
    sfpentru

afiseaza():
    k ← 1
    pentru i ← 2, n execută
        dacă L[i] > L[k] atunci k ← i sfdacă
    sfpentru
    scrie L[k]
    cât timp k ≠ 0 execută
        scrie a[k]; k ← urm[k]
    sfcât timp

citește n, a[1], …, a[n]
pDinamica()
afiseaza()

// L[i] = 0: subproblema i nu a fost rezolvată
lungime(i):
    dacă L[i] = 0 atunci
        L[i] ← 1; urm[i] ← 0
        pentru j ← i + 1, n execută
            dacă a[i] < a[j] și lungime(j) + 1 > L[i] atunci
                L[i] ← L[j] + 1; urm[i] ← j
            sfdacă
        sfpentru
    sfdacă
    returnează L[i]

afiseaza():
    k ← 1
    pentru i ← 2, n execută
        dacă L[i] > L[k] atunci k ← i sfdacă
    sfpentru
    scrie L[k]
    cât timp k ≠ 0 execută
        scrie a[k]; k ← urm[k]
    sfcât timp

citește n, a[1], …, a[n]
pentru i ← 1, n execută lungime(i) sfpentru
afiseaza()

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX], L[MAX], urm[MAX], n;

void citire() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
}

/* L[i] = lungimea celui mai lung subsir strict crescator
   care incepe cu a[i]; urm[i] = indicele termenului care
   urmeaza dupa a[i] in acel subsir (0 daca nu urmeaza
   niciunul). Tabelul se completeaza de la dreapta la
   stanga: L[i] se calculeaza din valorile L[j], j > i. */
void pDinamica() {
    for (int i = n; i >= 1; i--) {
        L[i] = 1;                   // subsirul format numai din a[i]
        urm[i] = 0;
        for (int j = i + 1; j <= n; j++)
            if (a[i] < a[j] && L[j] + 1 > L[i]) {
                L[i] = L[j] + 1;    // a[i], urmat de subsirul optim care incepe cu a[j]
                urm[i] = j;
            }
    }
}

void afiseaza() {
    int k = 1;                      // subsirul maxim incepe cu a[k]
    for (int i = 2; i <= n; i++)
        if (L[i] > L[k])
            k = i;
    cout << L[k] << "\n";
    while (k != 0) {                // construirea solutiei
        cout << a[k] << " ";
        k = urm[k];
    }
}

int main() {
    citire();
    pDinamica();
    afiseaza();
    return 0;
}

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX], L[MAX], urm[MAX], n;

void citire() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
}

/* Intoarce lungimea celui mai lung subsir strict crescator
   care incepe cu a[i]. L[i] = 0 inseamna ca subproblema i
   nu a fost inca rezolvata; orice lungime calculata este
   cel putin 1, deci valoarea 0 nu se confunda cu un rezultat. */
int lungime(int i) {
    if (L[i] == 0) {                // subproblema se rezolva o singura data
        L[i] = 1;
        urm[i] = 0;
        for (int j = i + 1; j <= n; j++)
            if (a[i] < a[j] && lungime(j) + 1 > L[i]) {
                L[i] = L[j] + 1;
                urm[i] = j;
            }
    }
    return L[i];                    // valoarea memorata
}

void afiseaza() {
    int k = 1;                      // subsirul maxim incepe cu a[k]
    for (int i = 2; i <= n; i++)
        if (L[i] > L[k])
            k = i;
    cout << L[k] << "\n";
    while (k != 0) {                // construirea solutiei
        cout << a[k] << " ";
        k = urm[k];
    }
}

int main() {
    citire();
    for (int i = 1; i <= n; i++)
        lungime(i);
    afiseaza();
    return 0;
}

def citire():
    n = int(input())
    a = [0] + [int(v) for v in input().split()]
    return n, a


# L[i] = lungimea celui mai lung subsir strict crescator
# care incepe cu a[i]; urm[i] = indicele termenului care
# urmeaza dupa a[i] in acel subsir (0 daca nu urmeaza
# niciunul). Tabelul se completeaza de la dreapta la
# stanga: L[i] se calculeaza din valorile L[j], j > i.
def p_dinamica(n, a):
    L = [0] * (n + 1)
    urm = [0] * (n + 1)
    for i in range(n, 0, -1):
        L[i] = 1                    # subsirul format numai din a[i]
        for j in range(i + 1, n + 1):
            if a[i] < a[j] and L[j] + 1 > L[i]:
                L[i] = L[j] + 1     # a[i], urmat de subsirul optim care incepe cu a[j]
                urm[i] = j
    return L, urm


def afiseaza(n, a, L, urm):
    k = 1                           # subsirul maxim incepe cu a[k]
    for i in range(2, n + 1):
        if L[i] > L[k]:
            k = i
    print(L[k])
    while k != 0:                   # construirea solutiei
        print(a[k], end=" ")
        k = urm[k]


n, a = citire()
L, urm = p_dinamica(n, a)
afiseaza(n, a, L, urm)

def citire():
    n = int(input())
    a = [0] + [int(v) for v in input().split()]
    return n, a


# Intoarce lungimea celui mai lung subsir strict crescator
# care incepe cu a[i]. L[i] = 0 inseamna ca subproblema i
# nu a fost inca rezolvata; orice lungime calculata este
# cel putin 1, deci valoarea 0 nu se confunda cu un rezultat.
def lungime(i):
    if L[i] == 0:                   # subproblema se rezolva o singura data
        L[i] = 1
        urm[i] = 0
        for j in range(i + 1, n + 1):
            if a[i] < a[j] and lungime(j) + 1 > L[i]:
                L[i] = L[j] + 1
                urm[i] = j
    return L[i]                     # valoarea memorata


def afiseaza():
    k = 1                           # subsirul maxim incepe cu a[k]
    for i in range(2, n + 1):
        if L[i] > L[k]:
            k = i
    print(L[k])
    while k != 0:                   # construirea solutiei
        print(a[k], end=" ")
        k = urm[k]


n, a = citire()
L = [0] * (n + 1)
urm = [0] * (n + 1)
for i in range(1, n + 1):
    lungime(i)
afiseaza()

Rezultatul nu este L[1]: subșirul maxim poate începe cu oricare termen, deci se caută cea mai mare valoare din L.

Pentru fiecare i se parcurg termenii de după el, deci se efectuează n(n − 1)/2 comparații, iar ordinul de complexitate este O(n²). Memoria suplimentară este O(n): vectorii L și urm. În varianta recursivă, adâncimea autoapelurilor este cel mult n.

Completarea vectorului L se poate urmări în simulatorul subșirului crescător maximal🔒.

Problema rucsacului în variantă discretă

Enunțul problemei

Un rucsac poate transporta o greutate de cel mult G. Se dau n obiecte; obiectul i are greutatea g[i] și aduce, dacă este transportat, profitul c[i]. Obiectele nu se pot fracționa: un obiect se ia întreg sau nu se ia deloc. Să se aleagă obiectele transportate astfel încât profitul total să fie maxim.

Date de intrare. Pe prima linie numerele naturale n și G (n ≤ 100, G ≤ 1000), pe fiecare dintre următoarele n linii greutatea și profitul unui obiect.

Date de ieșire. Pe prima linie profitul maxim, pe a doua numerele de ordine ale obiectelor alese, începând cu ultimul.

De ce nu se aplică metoda greedy

Se consideră un rucsac cu G = 6 și obiectele următoare:

Metoda greedy ia obiectele în ordinea descrescătoare a profitului pe unitatea de greutate: obiectul 1, apoi obiectul 3 (obiectul 2 nu mai încape), apoi obiectul 4. Greutatea totală este 6, iar profitul 20. Obiectele 2 și 3 au împreună tot greutatea 6, dar profitul 21.

Criteriul care dă soluția optimă la varianta continuă, descrisă în lecția despre metoda greedy, nu mai garantează optimul când obiectele nu se pot fracționa.

Ideea de rezolvare

Se notează cu C[i][j] profitul maxim care se obține alegând numai dintre primele i obiecte, într-un rucsac cu greutatea disponibilă j. Pentru obiectul i se compară situațiile următoare:

• obiectul i nu se ia — profitul maxim este cel obținut cu primele i − 1 obiecte și aceeași greutate disponibilă, adică C[i−1][j];
• obiectul i se ia, dacă g[i] ≤ j — greutatea rămasă, j − g[i], se încarcă optim cu primele i − 1 obiecte, deci profitul este C[i−1][j − g[i]] + c[i].

Dacă încărcarea optimă pentru (i, j) conține obiectul i, atunci celelalte obiecte alese formează o încărcare optimă pentru (i − 1, j − g[i]); altfel, înlocuirea lor cu o încărcare mai bună ar mări profitul total. Problema are, așadar, substructură optimă, iar relația de recurență este:

C[0][j] = 0,                                          pentru 0 ≤ j ≤ G
C[i][j] = C[i−1][j],                                  dacă g[i] > j
C[i][j] = max(C[i−1][j], C[i−1][j − g[i]] + c[i]),    dacă g[i] ≤ j

Subproblemele nu sunt independente: toate valorile de pe linia i se calculează din valorile liniei i − 1. Tabelul se completează linie cu linie, iar profitul maxim este C[n][G].

Exemplul pentru G = 6

Pentru obiectele din tabelul de mai sus se obține:

De exemplu, C[3][6] = max(C[2][6], C[2][4] + 7) = max(14, 21) = 21: obiectul 3 se ia, iar greutatea rămasă, 4, se încarcă optim cu primele două obiecte.

Obiectele alese se află pornind din C[4][6] și comparând fiecare valoare cu cea de deasupra ei:

• C[4][6] = 21 = C[3][6], deci obiectul 4 nu se ia;
• C[3][6] = 21 ≠ C[2][6] = 14, deci obiectul 3 se ia, iar greutatea disponibilă devine 6 − 2 = 4;
• C[2][4] = 14 ≠ C[1][4] = 12, deci obiectul 2 se ia, iar greutatea disponibilă devine 4 − 4 = 0;
• C[1][0] = 0 = C[0][0], deci obiectul 1 nu se ia.

Se transportă obiectele 2 și 3, cu greutatea totală 6 și profitul 21.

Programul

pDinamica():
    pentru j ← 0, G execută C[0][j] ← 0 sfpentru
    pentru i ← 1, n execută
        pentru j ← 0, G execută
            C[i][j] ← C[i − 1][j]
            dacă g[i] ≤ j și
                 C[i − 1][j − g[i]] + c[i] > C[i][j] atunci
                C[i][j] ← C[i − 1][j − g[i]] + c[i]
            sfdacă
        sfpentru
    sfpentru

afiseaza():
    scrie C[n][G]
    j ← G
    pentru i ← n, 1, −1 execută
        dacă C[i][j] ≠ C[i − 1][j] atunci
            scrie i; j ← j − g[i]
        sfdacă
    sfpentru

citește n, G și perechile g[i], c[i]
pDinamica()
afiseaza()

// C[i][j] = −1: subproblema (i, j) nu a fost rezolvată
profit(i, j):
    dacă i = 0 atunci returnează 0 sfdacă
    dacă C[i][j] = −1 atunci
        C[i][j] ← profit(i − 1, j)
        dacă g[i] ≤ j atunci
            cuObiect ← profit(i − 1, j − g[i]) + c[i]
            dacă cuObiect > C[i][j] atunci
                C[i][j] ← cuObiect
            sfdacă
        sfdacă
    sfdacă
    returnează C[i][j]

afiseaza():
    scrie profit(n, G)
    j ← G
    pentru i ← n, 1, −1 execută
        dacă profit(i, j) ≠ profit(i − 1, j) atunci
            scrie i; j ← j − g[i]
        sfdacă
    sfpentru

citește n, G și perechile g[i], c[i]
C[i][j] ← −1, pentru orice i și j
afiseaza()

#include <iostream>
using namespace std;

int g[101], c[101], C[101][1001], n, G;

void citire() {
    cin >> n >> G;
    for (int i = 1; i <= n; i++)
        cin >> g[i] >> c[i];
}

/* C[i][j] = profitul maxim obtinut numai cu primele i
   obiecte, pentru greutatea disponibila j. Linia 0 are
   numai valori 0 (tabloul global este initializat cu 0),
   iar fiecare linie se calculeaza din linia precedenta. */
void pDinamica() {
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= G; j++) {
            C[i][j] = C[i - 1][j];                  // obiectul i nu se ia
            if (g[i] <= j && C[i - 1][j - g[i]] + c[i] > C[i][j])
                C[i][j] = C[i - 1][j - g[i]] + c[i]; // obiectul i se ia
        }
}

/* Obiectul i a fost luat daca valoarea din tabel difera de
   cea obtinuta fara el, de pe linia de deasupra. */
void afiseaza() {
    cout << C[n][G] << "\n";
    int j = G;
    for (int i = n; i >= 1; i--)
        if (C[i][j] != C[i - 1][j]) {
            cout << i << " ";
            j = j - g[i];
        }
}

int main() {
    citire();
    pDinamica();
    afiseaza();
    return 0;
}

#include <iostream>
using namespace std;

int g[101], c[101], C[101][1001], n, G;

void citire() {
    cin >> n >> G;
    for (int i = 1; i <= n; i++)
        cin >> g[i] >> c[i];
}

/* Intoarce profitul maxim obtinut numai cu primele i obiecte,
   pentru greutatea disponibila j. Profitul 0 este un rezultat
   posibil, deci subproblemele nerezolvate se marcheaza cu -1. */
int profit(int i, int j) {
    if (i == 0)
        return 0;                       // niciun obiect
    if (C[i][j] == -1) {                // subproblema se rezolva o singura data
        C[i][j] = profit(i - 1, j);     // obiectul i nu se ia
        if (g[i] <= j) {
            int cuObiect = profit(i - 1, j - g[i]) + c[i];
            if (cuObiect > C[i][j])
                C[i][j] = cuObiect;     // obiectul i se ia
        }
    }
    return C[i][j];
}

void afiseaza() {
    cout << profit(n, G) << "\n";
    int j = G;
    for (int i = n; i >= 1; i--)
        if (profit(i, j) != profit(i - 1, j)) {
            cout << i << " ";
            j = j - g[i];
        }
}

int main() {
    citire();
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= G; j++)
            C[i][j] = -1;
    afiseaza();
    return 0;
}

def citire():
    n, G = map(int, input().split())
    g, c = [0], [0]
    for _ in range(n):
        gi, ci = map(int, input().split())
        g.append(gi)
        c.append(ci)
    return n, G, g, c


# C[i][j] = profitul maxim obtinut numai cu primele i
# obiecte, pentru greutatea disponibila j. Linia 0 are
# numai valori 0, iar fiecare linie se calculeaza din
# linia precedenta.
def p_dinamica(n, G, g, c):
    C = [[0] * (G + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(G + 1):
            C[i][j] = C[i - 1][j]                   # obiectul i nu se ia
            if g[i] <= j and C[i - 1][j - g[i]] + c[i] > C[i][j]:
                C[i][j] = C[i - 1][j - g[i]] + c[i]  # obiectul i se ia
    return C


# Obiectul i a fost luat daca valoarea din tabel difera de
# cea obtinuta fara el, de pe linia de deasupra.
def afiseaza(n, G, g, C):
    print(C[n][G])
    j = G
    for i in range(n, 0, -1):
        if C[i][j] != C[i - 1][j]:
            print(i, end=" ")
            j = j - g[i]


n, G, g, c = citire()
C = p_dinamica(n, G, g, c)
afiseaza(n, G, g, C)

def citire():
    n, G = map(int, input().split())
    g, c = [0], [0]
    for _ in range(n):
        gi, ci = map(int, input().split())
        g.append(gi)
        c.append(ci)
    return n, G, g, c


# Intoarce profitul maxim obtinut numai cu primele i obiecte,
# pentru greutatea disponibila j. Profitul 0 este un rezultat
# posibil, deci subproblemele nerezolvate se marcheaza cu -1.
def profit(i, j):
    if i == 0:
        return 0                        # niciun obiect
    if C[i][j] == -1:                   # subproblema se rezolva o singura data
        C[i][j] = profit(i - 1, j)      # obiectul i nu se ia
        if g[i] <= j:
            cu_obiect = profit(i - 1, j - g[i]) + c[i]
            if cu_obiect > C[i][j]:
                C[i][j] = cu_obiect     # obiectul i se ia
    return C[i][j]


def afiseaza():
    print(profit(n, G))
    j = G
    for i in range(n, 0, -1):
        if profit(i, j) != profit(i - 1, j):
            print(i, end=" ")
            j = j - g[i]


n, G, g, c = citire()
C = [[-1] * (G + 1) for _ in range(n + 1)]
afiseaza()