0/1 Oprava problému s batohem pomocí příkladu dynamického programování

Co je problém batohu?

Jedno Problém s batohem je klasický kombinatorický optimalizační problém. Supermarket obchoduje n balíčky (n ≤ 100). Balíček i má hmotnost W[i] ≤ 100 a hodnotu V[i] ≤ 100. Zloděj nemůže unést hmotnost přesahující nosnost M (M ≤ 100). Které balíky by si měl zloděj vzít, aby maximalizoval celkovou hodnotu?

Vstup:

• Maximální hmotnost M a počet balíků n.
• Pole hmotnosti W[i] a odpovídající hodnoty V[i].

Výstup:

• Maximální celková hodnota dosažitelná v rámci kapacity.
• Přesná sada balíků, které by si měl zloděj vzít.

Algoritmus Knapsack se dělí na dvě známé varianty:

• Problém s batohem 0/1 řešeno dynamickým programováním. Každý balíček je buď převzat celý, nebo ponechán – žádné zlomkové části a žádné duplikáty.
• Problém frakčního batohu vyřešeno chamtivou strategií. Zde si můžete vzít zlomek libovolného balíčku, abyste zaplnili zbývající kapacitu.

Jak vyřešit problém s batohem pomocí dynamického programování s příkladem

Metoda „rozděl a panuj“ rozděluje velký problém na dílčí problémy a v dělení pokračuje, dokud každý dílčí problém není snadný. Prostá rekurze však často řeší stejný dílčí problém mnohokrát a plýtvá prací.

Základní myšlenkou dynamického programování v Knapsack je uložit každý vyřešený dílčí problém do tabulky. Opakovaná volání přečtou odpověď, místo aby ji znovu přepočítali, čímž se exponenciální rekurze přemění na kód s polynomiálním časem.

Vyřešte problém s batohem pomocí dynamického programování

Pro návrh řešení dynamického programování je třeba postupovat ve čtyřech krocích:

• Nejprve vyřešte nejmenší dílčí problémy.
• Odvodte rekurenci, která sestaví řešení dílčího problému z menších řešení.
• Uložte odpovědi na dílčí problémy do tabulky vypočítané zdola nahoru pomocí opakování.
• Konečnou odpověď sestavte z plně vyplněné tabulky.

Analyzujte problém batohu 0/1

Optimální hodnota závisí na dvou nezávislých faktorech:

1. Kolik balíčků se stále zvažuje.
2. Zbývající hmotnost, kterou batoh ještě pojme.

Protože účelová funkce závisí na dvou veličinách, musí být tabulka možností dvourozměrná. Nechť B[i][j] označují maximální hodnotu při výběru mezi balíky {1, …, i} s hmotnostním limitem j.

• Konečná odpověď je B[n][M], nejlepší celková hodnota napříč všemi n balíčky v rámci kapacity M.
• Celková vybraná hmotnost je vždy omezena aktuální kapacitou: B[i][j] ≤ j.

Příklad: pokud B[4][10] = 8, nejlepší celková hmotnost z prvních čtyř balíků pod kapacitou 10 je 8. Některé z těchto čtyř balíků mohou být vynechány.

Vzorec pro výpočet B[i][j]

• W[i], V[i] jsou hmotnost a hodnota balíku i, kde i je v {1, …, n}.
• M je maximální hmotnost, kterou batoh unese.

Základní případ s jedním pouzdrem: pro každou kapacitu j ≥ W[1]:

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

V obecném případě rozhodněte, zda zahrnout balíček i pod kapacitu j:

• Pokud je balíček i přeskočeno, B[i][j] se rovná nejlepší hodnotě s využitím balíčků {1, …, i-1} s kapacitou j:

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

• Pokud je balíček i zaujatý (povoleno pouze tehdy, když W[i] ≤ j), B[i][j] se rovná V[i] plus nejlepší hodnota z balíčků {1, …, i-1} pod kapacitou j – W[i]:

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

Vezměte si většího z obou kandidátů.

Základy dynamického programování

Kombinací obou případů získáme úplnou rekurentnost:

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

Základní případ je B[0][j] = 0 pro každé j, protože nula balíčků dává nulovou hodnotu bez ohledu na kapacitu.

Vypočítejte tabulku možností

Sestavte B pomocí opakování. Jakmile je B naplněna, stejná tabulka řídí trace-back, který rekonstruuje vybrané balíčky. Tabulka B má n + 1 řádků a M + 1 sloupců:

• Řádek 0 je základní případ, vyplněný nulami.
• Použijte řádek 0 k výpočtu řádku 1, řádek 1 k výpočtu řádku 2 a pokračujte, dokud není řádek n kompletní.

Tabulka možností

Trace

Jakmile je B hotové, zaměřte se na B[n][M], optimální celková hodnota napříč všemi n balíky s kapacitou M.

• If B[n][M] = B[n-1][M], balíček n nebyl vybrán, takže pokračujte tracz B[n-1][M].
• If B[n][M] ≠ B[n-1][M], byl vybrán balíček n, takže pokračujte tracz B[n-1][M – W[n]].

Opakujte, dokud se nedostanete k řádku 0 tabulky.

Algoritmus pro vyhledání vybraných balíčků v tabulce možností

Poznámka: kdykoli B[i][j] = B[i-1][j], balíček i není vybrán. Hodnota B[n][M] je optimální celková hodnota zabalená do batohu.

Kroky pro tracvybrané balíčky:

• Krok 1: Začněte v i = n, j = M.
• Krok 2: Prohledejte sloupec j zdola nahoru, dokud nenajdete řádek i, kde B[i][j] > B[i-1][j]. Označte balíček i jako vybraný: Select[i] = true.
• Krok 3: Aktualizace j = j – W[i]. Pokud j > 0, vraťte se ke kroku 2, jinak přejděte ke kroku 4.
• Krok 4: Vytiskněte všechny označené balíčky.

Java Code

Následující Java Metoda vyplní B[][] zdola nahoru, vytiskne tabulku pro kontrolu a poté tracvybrané balíčky.

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--;
    }
}

Funkce knapsackDyProg() in Java

Vysvětlení kódu:

1. Alokovat tabulku B[][] a inicializovat každou buňku na 0.
2. Vyplňte B[][] zdola nahoru pomocí opakování z předchozí části.
3. Začněte každou buňku hodnotou „přeskočit balíček i“. B[i-1][j].
4. Pokud je výběr balíčku i proveditelný a dává striktně lepší hodnotu, přepište buňku.
5. Tracvybrané položky z řádku n zpět do řádku 0.
6. Kdykoli je vybrán balíček n, snižte zbývající kapacitu o W[n-1].

Oprava poznámky: původní parametr mutovaného úryvku M při čtení B[n][M]Bezpečnější verze výše používá samostatný kurzor. j pro trace.

Jedno Java Řidič spustí algoritmus na dvou zpracovaných příkladech:

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);
}

Výstup pro první příklad:

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

Výstup pro druhý příklad:

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

Časová a prostorová složitost batohu 0/1

• Časová složitost: O(n · M) — dvě vnořené smyčky procházejí n položkami napříč M+1 stavy kapacity.
• Složitost prostoru: O(n · M) pro celou tabulku, redukovatelné na O(M) pomocí keeping pouze předchozí řádek, když tracElektronická zpětná vazba není nutná.

Běhová doba je pseudopolynom: polynom v hodnotě M, ale exponenciální v bitech použitých ke kódování M. Proto zůstává Knapsack typu 0/1 NP-těžký, i když je dynamické programování v praxi efektivní.

Aplikace problému batohu 0/1

• Nakládka nákladu, balení kontejnerů a vychystávání ve skladu do hmotnostních limitů.
• Rozdělení rozpočtu mezi investiční projekty s fixními náklady a očekávanou návratností.
• Problémy s řezáním materiálu ve výrobě, které nedokáže rozdělit jednotlivé kusy.
• Kryptografické schémata jako Merkle-Hellman, která staví na tvrdosti batohu.
• Plánování s omezenými zdroji v cloud computingu a umístění úloh CPU.
• Výběr funkcí ve strojovém učení s pevným rozpočtem funkcí.

Nejčastější dotazy