0/1 Seljakotiprobleemide lahendamine dünaamilise programmeerimise näite abil

Mis on seljakoti probleem?

. Seljakoti probleem on klassikaline kombinatoorne optimeerimisülesanne. Supermarketis on kauplused n paketid (n ≤ 100). Pakett i mille kaal W[i] ≤ 100 ja väärtus V[i] ≤ 100. Varas ei saa kanda raskust, mis ületab kandevõime M (M ≤ 100). Milliseid pakke peaks varas kaasa võtma, et koguväärtust maksimeerida?

sisend:

• Maksimaalne kaal M ja pakendite arv n.
• Massiivi massi W[i] ja vastava väärtuse V[i].

Väljund:

• Mahuvuse piires saavutatav maksimaalne koguväärtus.
• Täpne pakkide komplekt, mis varas peaks kaasa võtma.

Knapsacki algoritm jaguneb kaheks tuntud variandiks:

• 0/1 Seljakoti probleem lahendatud dünaamilise programmeerimise abil. Iga pakett võetakse kas tervikuna või jäetakse alles – ei mingeid murdosasid ega duplikaate.
• Fraktsionaalse seljakoti probleem lahendatud ahne strateegiaga. Siin võid võtta murdosa mis tahes pakist, et täita ülejäänud maht.

Kuidas lahendada seljakotiprobleemi näitega dünaamilise programmeerimise abil

Jaga-ja-valitse meetod jagab suure probleemi alamprobleemideks ja jätkab jagamist seni, kuni iga alamprobleem on lihtne. Lihtne rekursioon aga lahendab sama alamprobleemi sageli mitu korda ja raiskab tööd.

Knapsacki dünaamilise programmeerimise põhiidee on salvestada iga lahendatud alamülesanne tabelisse. Korduvad väljakutsed loevad vastuse uuesti arvutamise asemel, muutes eksponentsiaalse rekursiooni polünoomse ajaga koodiks.

Lahendage seljakotiprobleem dünaamilise programmeerimise abil

Dünaamilise programmeerimise lahenduse kujundamiseks järgige nelja sammu:

• Lahenda kõigepealt kõige väiksemad alamprobleemid.
• Tuleta rekurrents, mis ehitab väiksematest rekurrentsidest üles alaprobleemi vastuse.
• Salvesta alamülesannete vastused tabelisse, mis on arvutatud alt-üles, kasutades rekurrentsi.
• Koguge lõplik vastus täielikult täidetud tabeli põhjal.

Analüüsige 0/1 seljakoti probleemi

Optimaalne väärtus sõltub kahest sõltumatust tegurist:

1. Mitu paketti veel kaalutakse?
2. Ülejäänud kaal, mida seljakott ikka mahutab.

Kuna eesmärgifunktsioon sõltub kahest suurusest, peab valikute tabel olema kahemõõtmeline. Olgu B[i][j] tähistame maksimaalset väärtust pakkide {1, …, i} hulgast valimisel kaalupiiranguga j.

• Lõplik vastus on B[n][M], parim koguväärtus kõigi n paketi peale mahutavuse M all.
• Valitud kogukaal on alati piiratud praeguse kandevõimega: B[i][j] ≤ j.

Näide: kui B[4][10] = 8, siis mahutavusega 10 alla jääva esimese nelja paki parim kogukaal on 8. Mõned neist neljast pakist võidakse vahele jätta.

Valem B[i][j] arvutamiseks

• W[i], V[i] on paki i kaal ja väärtus, kus i asub hulgas {1, …, n}.
• M on seljakoti maksimaalne kandevõime.

Baasjuhtum ühe pakendiga: iga mahutavuse j ≥ W[1] korral:

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

Üldjuhul otsustage, kas lisada pakett i mahutavuse j alla:

• Kui pakett i on vahele jäetud, B[i][j] võrdub parima väärtusega, mis on saadud pakettide {1, …, i-1} abil mahutavuse j korral:

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

• Kui pakett i on võtnud (lubatud ainult siis, kui W[i] ≤ j), B[i][j] võrdub V[i]-ga pluss parim väärtus pakettidest {1, …, i-1} mahutavuse j – W[i] all:

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

Võtke kahest kandidaadist suurem.

Dünaamilise programmeerimise alused

Kahe juhtumi kombineerimine annab täieliku korduvuse:

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

Põhijuhtum on B[0][j] = 0 iga j korral, sest nullpakendid annavad nullväärtuse olenemata mahutavusest.

Arvutage valikute tabel

Loo B rekurrentsi abil. Kui B on täidetud, käivitab sama tabel ka trace-tagasi, mis rekonstrueerib valitud paketid. Tabelis B on n + 1 rida ja M + 1 veergu:

• Rida 0 on baasjuhtum, mis on täidetud nullidega.
• Kasutage rida 0 rea 1 arvutamiseks, rida 1 rea 2 arvutamiseks ja jätkake, kuni rida n on valmis.

Valikute tabel

Trace

Kui B on valmis, keskendu sellele B[n][M], optimaalne koguväärtus kõigi n paketi puhul mahutavusega M.

• If B[n][M] = B[n-1][M], paketti n ei valitud, seega jätka tracmine B[n-1][M]-ist.
• If B[n][M] ≠ B[n-1][M], pakett n valiti, seega jätkake tracmine alates B[n-1][M – W[n]].

Korda, kuni jõuad tabeli rea 0-ni.

Algoritm valitud pakettide leidmiseks valikute tabeli otsimiseks

Märkus: alati, kui B[i][j] = B[i-1][j], paketti i pole valitud. Väärtus B[n][M] on seljakotti pakitud optimaalne koguväärtus.

Sammud tracvalitud pakettide kasutamine:

• Samm 1: Alustame punktist i = n, j = M.
• Samm 2: Skannige veergu j alt ülespoole, kuni leiate rea i, kus B[i][j] > B[i-1][j]. Märkige pakett i valituks: Select[i] = true.
• Samm 3: Uuenda j = j – W[i]. Kui j > 0, naase 2. sammu juurde, vastasel juhul mine 4. sammu juurde.
• Samm 4: Prindi kõik valitud pakendid.

Java Code

Järgmised Java meetod täidab tabeli B[][] alt-üles, prindib tabeli kontrollimiseks ja seejärel traces valitud paketid.

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

Funktsioon knapsackDyProg() in Java

Koodi selgitus:

1. Tabeli eraldamine B[][] ja initsialiseeri iga lahter väärtuseks 0.
2. Täida B[][] alt-üles, kasutades eelmises jaotises kirjeldatud rekurrentsi.
3. Alusta iga lahtrit väärtusega „jäta pakett i vahele” B[i-1][j].
4. Kui paketi i valimine on teostatav ja annab rangelt parema väärtuse, kirjutage lahter üle.
5. Trace valitud üksused realt n tagasi reale 0.
6. Kui valitakse pakett n, vähendage järelejäänud mahtu võrra W[n-1].

Paranda märkus: algse koodilõigu muteeritud parameeter M ikka veel lugedes B[n][M]Ülaltoodud turvalisem versioon kasutab eraldi kursorit. j jaoks trace.

. Java Draiver käivitab algoritmi kahel töötatud näitel:

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

Esimese näite väljund:

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

Teise näite väljund:

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

0/1 seljakoti aja ja ruumi keerukus

• Ajaline keerukus: O(n · M) — kaks pesastatud tsüklit läbivad n elementi M+1 mahutavuse olekutes.
• Ruumi keerukus: O(n · M) täistabeli jaoks, taandatav väärtusele O(M) käsuga keeping ainult eelmine rida, kui trace-tagasi pole vaja.

Käitusaeg on pseudopolünoompolünoom M väärtuses, kuid eksponentsiaalne M kodeerimiseks kasutatavate bittide osas. Seetõttu jääb 0/1 Knapsack NP-raskeks, kuigi dünaamiline programmeerimine on praktikas efektiivne.

0/1 seljakotiprobleemi rakendused

• Kauba laadimine, konteinerite pakkimine ja laost komplekteerimine kaalupiirangute piires.
• Eelarve jaotus investeerimisprojektide vahel fikseeritud kulude ja oodatava tootlusega.
• Lõikevarude probleemid tootmises, mille puhul ei ole võimalik üksikuid tükke jagada.
• Krüptograafiaskeemid, näiteks Merkle-Hellmani meetod, mis tuginevad seljakoti kõvadusele.
• Ressursside poolt piiratud ajastamine pilvandmetöötluses ja protsessori ülesannete paigutus.
• Funktsioonide valik masinõppes fikseeritud funktsioonide eelarve piires.

KKK