0/1 Problemă la rucsac Remediere folosind un exemplu de programare dinamică

Care este problema rucsacului?

Problemă la rucsac este o problemă clasică de optimizare combinatorie. Un supermarket comercializează n pachete (n ≤ 100). Pachet i are greutatea W[i] ≤ 100 și valoarea V[i] ≤ 100. Un hoț nu poate transporta o greutate care depășește capacitatea M (M ≤ 100). Ce colete ar trebui să ia hoțul pentru a maximiza valoarea totală?

Intrare:

• Greutatea maximă M și numărul de pachete n.
• Matrice de greutate W[i] și valoarea corespunzătoare V[i].

ieșire:

• Valoare totală maximă obținută în cadrul capacității.
• Setul exact de pachete pe care ar trebui să le ia hoțul.

Algoritmul Knapsack se împarte în două variante binecunoscute:

• Problema rucsacului 0/1 rezolvată prin Programare Dinamică. Fiecare pachet este fie luat în întregime, fie lăsat în urmă — fără fragmente și fără duplicate.
• Problema rucsacului fracționat rezolvată printr-o strategie lacomă. Aici poți lua o fracțiune din orice pachet pentru a umple capacitatea rămasă.

Cum se rezolvă problema rucsacului folosind programarea dinamică cu exemplu

Metoda „împarte și cucerește” împarte o problemă mare în subprobleme, apoi continuă să împartă până când fiecare subproblemă devine ușoară. Recursivitatea simplă, însă, rezolvă adesea aceeași subproblemă de mai multe ori și irosește efort.

Ideea centrală a programării dinamice Knapsack este de a stoca fiecare subproblemă rezolvată într-un tabel. Apelurile repetate citesc răspunsul în loc să îl recalculeze, transformând o recursiune exponențială într-un cod de timp polinomial.

Rezolvați problema rucsacului folosind programarea dinamică

Pentru a proiecta o soluție de Programare Dinamică, urmați patru pași:

• Rezolvă mai întâi cele mai mici subprobleme.
• Derivați o recurență care construiește un răspuns la o subproblemă din unele mai mici.
• Stocați răspunsurile la subprobleme într-un tabel calculat de jos în sus folosind recurența.
• Asamblați răspunsul final din tabelul complet completat.

Analizați problema rucsacului 0/1

Valoarea optimă depinde de doi factori independenți:

1. Câte pachete sunt încă luate în considerare.
2. Greutatea rămasă pe care rucsacul o mai poate stoca.

Deoarece funcția obiectiv depinde de două mărimi, tabelul de opțiuni trebuie să fie bidimensional. Fie B[i][j] reprezintă valoarea maximă la alegerea dintre pachetele {1, …, i} cu limita de greutate j.

• Răspunsul final este B[n][M], cea mai bună valoare totală din toate cele n pachete sub capacitatea M.
• Greutatea totală selectată este întotdeauna limitată de capacitatea curentă: B[i][j] ≤ j.

Exemplu: dacă B[4][10] = 8, cea mai bună greutate totală din primele patru pachete sub capacitatea 10 este 8. Este posibil ca unele dintre aceste patru pachete să fie omise.

Formula pentru a calcula B[i][j]

• W[i], V[i] sunt greutatea și valoarea pachetului i, unde i se află în {1, …, n}.
• M este greutatea maximă pe care o poate suporta rucsacul.

Caz de bază cu un singur pachet: pentru fiecare capacitate j ≥ W[1]:

B[1][j] = W[1]

Pentru cazul general, decideți dacă să includeți pachetul i în capacitatea j:

• Dacă pachetul i este omit, B[i][j] este egal cu cea mai bună valoare folosind pachetele {1, …, i-1} sub capacitatea j:

B[i][j] = B[i - 1][j]

• Dacă pachetul i este luate (permis doar când W[i] ≤ j), B[i][j] este egal cu V[i] plus cea mai bună valoare din pachetele {1, …, i-1} sub capacitatea j – W[i]:

B[i][j] = V[i] + B[i - 1][j - W[i]]

Luați-l pe cel mai mare dintre cei doi candidați.

Baza programării dinamice

Combinând cele două cazuri se obține recurența completă:

B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])

Cazul de bază este B[0][j] = 0 pentru fiecare j, deoarece pachetele zero dau valoare zero indiferent de capacitate.

Calculați tabelul de opțiuni

Construiți B folosind recurența. Odată ce B este umplut, același tabel controlează trace-back care reconstruiește pachetele alese. Tabelul B are n + 1 rânduri și M + 1 coloane:

• Rândul 0 este cazul de bază, umplut cu zerouri.
• Folosește rândul 0 pentru a calcula rândul 1, rândul 1 pentru a calcula rândul 2 și continuă până când rândul n este complet.

Tabel de Opțiuni

Trace

Odată ce B este complet, concentrați-vă pe B[n][M], valoarea totală optimă pentru toate cele n pachete cu capacitatea M.

• If B[n][M] = B[n-1][M], pachetul n nu a fost selectat, deci continuați tracprovenind din B[n-1][M].
• If B[n][M] ≠ B[n-1][M], pachetul n a fost selectat, deci continuați tracprovenind de la B[n-1][M – W[n]].

Repetați până ajungeți la rândul 0 al tabelului.

Algoritm pentru a căuta tabelul de opțiuni pentru a găsi pachetele selectate

Notă: oricând B[i][j] = B[i-1][j], pachetul i nu este selectat. Valoarea B[n][M] este valoarea totală optimă încadrată în rucsac.

Pași pentru tracpachetele alese:

• Pasul 1: Începeți de la i = n, j = M.
• Pasul 2: Scanați coloana j de jos în sus până găsiți un rând i unde B[i][j] > B[i-1][j]. Marcați pachetul i ca selectat: Select[i] = true.
• Pasul 3: Actualizați j = j – W[i]. Dacă j > 0, reveniți la Pasul 2, altfel treceți la Pasul 4.
• Pasul 4: Imprimați fiecare pachet marcat ca selectat.

Java Code

Următoarele Java metoda umple B[][] de jos în sus, imprimă tabelul pentru inspecție și apoi traceste pachetele selectate.

public void knapsackDyProg(int W[], int V[], int M, int n) {
    int B[][] = new int[n + 1][M + 1];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= M; j++) {
            B[i][j] = 0;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            B[i][j] = B[i - 1][j];

            if ((j >= W[i - 1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
                B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
            }

            System.out.print(B[i][j] + " ");
        }
        System.out.print("\n");
    }

    System.out.println("Max Value:\t" + B[n][M]);
    System.out.println("Selected Packs: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

Funcția knapsackDyProg() în Java

Explicația codului:

1. Alocare tabel B[][] și inițializează fiecare celulă la 0.
2. Completați B[][] de jos în sus folosind recurența din secțiunea anterioară.
3. Începeți fiecare celulă cu valoarea „săriți pachetul i” B[i-1][j].
4. Dacă alegerea pachetului i este fezabilă și oferă o valoare strict mai bună, suprascrieți celula.
5. Tracreaduce elementele selectate din rândul n înapoi în rândul 0.
6. Ori de câte ori este ales pachetul n, se reduce capacitatea rămasă cu W[n-1].

Notă de corecție: parametrul original al fragmentului mutat M în timp ce încă citesc B[n][M]Versiunea mai sigură de mai sus folosește un cursor separat. j pentru trace.

Java Driverul rulează algoritmul pe două exemple funcționale:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

Rezultatul pentru primul exemplu:

0 0 0 3 3 3 3 3 3 3 3 3
0 0 0 3 4 4 4 7 7 7 7 7
0 0 0 3 4 4 4 7 7 8 8 8
0 0 0 3 4 4 4 7 7 10 10 10
0 0 0 3 4 4 4 7 8 10 10 11
Max Value:	11
Selected Packs:
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

Rezultatul pentru al doilea exemplu:

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs:
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

Complexitatea timpului și spațiului unui rucsac 0/1

• Complexitatea timpului: O(n · M) — cele două bucle imbricate parcurg n elemente prin M+1 stări de capacitate.
• Complexitatea spațiului: O(n · M) pentru tabelul complet, reductibil la O(M) prin keeping doar rândul anterior când tracNu este necesar un e-back.

Timpul de rulare este pseudo-polinom: polinom în valoarea lui M, dar exponențial în biții utilizați pentru a codifica M. De aceea, Knapsack 0/1 rămâne NP-hard chiar dacă programarea dinamică este eficientă în practică.

Aplicații ale problemei rucsacului 0/1

• Încărcarea mărfurilor, ambalarea containerelor și picking din depozit în limitele de greutate.
• Alocarea bugetului între proiecte de investiții cu costuri fixe și randament așteptat.
• Probleme legate de stocul de prelucrare în producție, care nu permit separarea pieselor individuale.
• Scheme de criptografie precum Merkle-Hellman care se bazează pe duritatea rucsacului.
• Planificarea cu resurse constrânse în cloud computing și plasarea sarcinilor CPU.
• Selecția caracteristicilor în învățarea automată cu un buget fix de caracteristici.

Întrebări frecvente