0/1 Hátizsák probléma megoldása dinamikus programozási példa segítségével

Mi a hátizsák probléma?

Az Hátizsák probléma egy klasszikus kombinatorikus optimalizálási probléma. Egy szupermarketben tárolják n csomagok (n ≤ 100). Csomag i Súlya W[i] ≤ 100 és értéke V[i] ≤ 100. Egy tolvaj nem tud M teherbírásnál nagyobb súlyt elszállítani (M ≤ 100). Melyik csomagokat kell a tolvajnak elvinnie a maximális összérték érdekében?

Bemenet:

• Maximális tömeg M és a csomagok száma n.
• W[i] súlytömb és a megfelelő V[i] érték.

output:

• A kapacitáson belül elérhető maximális összérték.
• A pontos csomagkészlet, amit a tolvajnak el kell vinnie.

A Knapsack algoritmus két jól ismert változatra oszlik:

• 0/1 Hátizsák probléma Dinamikus programozással megoldva. Minden csomagot vagy egészben vesznek el, vagy otthagynak – nincsenek töredékek és nincsenek duplikátumok.
• Töredékes hátizsák probléma egy Mohó Stratégiával megoldható. Itt bármelyik csomag egy részét elveheted, hogy kitöltsd a fennmaradó kapacitást.

Hátizsákprobléma megoldása dinamikus programozással példával

Az oszd meg és uralkodj módszer egy nagy problémát részproblémákra bont, majd addig folytatja a felosztást, amíg minden részprobléma könnyűvé nem válik. A sima rekurzió azonban gyakran ugyanazt a részproblémát sokszor megoldja, és munkát pazarol.

A Knapsack dinamikus programozás alapötlete, hogy minden megoldott részproblémát egy táblázatban tároljon. Az ismételt hívások a választ újraszámítás helyett beolvassák, így az exponenciális rekurzió polinom idejű kóddá alakul.

Oldja meg a hátizsák problémáját dinamikus programozással

Dinamikus programozási megoldás megtervezéséhez négy lépést kell követni:

• Először a legkisebb részproblémákat oldd meg.
• Származtasson egy olyan rekurrenciát, amely kisebb rekurrenciákból épít fel egy részprobléma megoldást.
• A részproblémák válaszait egy táblázatban tároljuk, alulról felfelé számítva a rekurzió függvény segítségével.
• Állítsd össze a végső választ a teljesen kitöltött táblázatból.

Elemezze a 0/1 hátizsák problémát

Az optimális érték két független tényezőtől függ:

1. Hány csomagot vesznek még figyelembe?
2. A hátizsák fennmaradó súlyát még elbírja.

Mivel a célfüggvény két mennyiségtől függ, a lehetőségek táblázatának kétdimenziósnak kell lennie. Legyen B[i][j] jelölje a maximális értéket, amikor a j súlykorláttal rendelkező {1, …, i} csomagok közül választunk.

• A végső válasz az B[n][M], a legjobb összérték az összes n csomag közül M kapacitás alatt.
• A kiválasztott teljes súlyt mindig az aktuális kapacitás korlátozza: B[i][j] ≤ j.

Példa: ha B[4][10] = 8, akkor a 10-es kapacitás alatti első négy csomag legjobb össztömege 8. E négy csomag közül néhány kihagyható.

Képlet a B[i][j] kiszámításához

• W[i], V[i] az i csomag súlya és értéke, ahol i az {1, …, n} intervallumban található.
• M a hátizsák maximális súlya.

Alapeset egy csomaggal: minden j ≥ W[1] kapacitás esetén:

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

Általános esetben döntse el, hogy az i csomagot belefoglalja-e a j kapacitásba:

• Ha az i. csomag átugrott, B[i][j] egyenlő a legjobb értékkel, amelyet j kapacitás mellett az {1, …, i-1} csomagok használatával kapunk:

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

• Ha az i. csomag meghozott (csak akkor engedélyezett, ha W[i] ≤ j), B[i][j] egyenlő V[i] plusz a j – W[i] kapacitás alatti {1, …, i-1} csomagok közül a legjobb érték:

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

Vegyük a két jelölt közül a nagyobbat.

A dinamikus programozás alapjai

A két eset kombinálása a teljes kiújulást adja:

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

Az alapeset a következő: B[0][j] = 0 minden j esetén, mivel a nulla csomagok nulla értéket adnak a kapacitástól függetlenül.

Számítsa ki az opciók táblázatát

Építsd fel a B táblázatot a rekurzió felhasználásával. Miután a B táblázat ki van töltve, ugyanaz a táblázat vezérli a következőt: tracegy e-back, amely rekonstruálja a kiválasztott csomagokat. A B táblázat n + 1 sort és M + 1 oszlopot tartalmaz:

• A 0. sor az alapeset, nullákkal kitöltve.
• A 0. sor segítségével számítsa ki az 1. sort, az 1. sorral a 2. sort, és folytassa, amíg az n. sor be nem fejeződik.

Lehetőségek táblázata

Trace

Miután a B rész elkészült, koncentrálj a következőre: B[n][M], az optimális összegérték az összes n darab, M kapacitású csomagra vonatkozóan.

• If B[n][M] = B[n-1][M], az n csomagot nem választottuk ki, ezért folytassuk tracB[n-1][M]-ből.
• If B[n][M] ≠ B[n-1][M], az n csomag lett kiválasztva, tehát folytasd tracB[n-1][M – W[n]]-ből.

Ismételd, amíg el nem éred a táblázat 0. sorát.

Algoritmus az opciók táblázatában a kiválasztott csomagok megkereséséhez

Megjegyzés: valahányszor B[i][j] = B[i-1][j], az i csomag nincs kiválasztva. Az érték B[n][M] a hátizsákba csomagolt optimális összérték.

Lépések traca kiválasztott csomagok kiválasztása:

• Lépés 1: Kezdjük i = n, j = M értékkel.
• Lépés 2: Végigfutjuk a j oszlopot alulról felfelé, amíg meg nem találjuk az i sort, ahol B[i][j] > B[i-1][j]. Jelöljük az i csomagot kiválasztottként: Select[i] = true.
• Lépés 3: Frissítse a j = j – W[i] képletet. Ha j > 0, térjen vissza a 2. lépéshez, egyébként folytassa a 4. lépéssel.
• Lépés 4: Nyomtasson ki minden kiválasztottként megjelölt csomagot.

Java Code

A következő Java a metódus alulról felfelé tölti ki a B[][] táblázatot, kinyomtatja a táblázatot ellenőrzés céljából, majd traca kiválasztott csomagokat.

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

A knapsackDyProg() függvény be Java

A kód magyarázata:

1. Tábla lefoglalása B[][] és inicializáljon minden cellát 0-ra.
2. Töltsd ki a B[][] mezőt alulról felfelé az előző szakaszban szereplő rekurzió felhasználásával.
3. Minden cellát a „kihagyás csomag i” értékkel kell kezdeni. B[i-1][j].
4. Ha az i-edik csomag kiválasztása megvalósítható és szigorúan véve jobb értéket ad, akkor írja felül a cellát.
5. Traca kiválasztott elemeket az n sortól vissza a 0 sorig.
6. Az n csomag kiválasztásakor a fennmaradó kapacitást csökkentse a következővel: W[n-1].

Javítási megjegyzés: az eredeti kódrészlet mutált paramétere M miközben még mindig olvas B[n][M]A fenti biztonságosabb verzió külön kurzort használ. j az trace.

Az Java Az illesztőprogram két működő példán futtatja le az algoritmust:

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

Az első példa kimenete:

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

A második példa kimenete:

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

A 0/1-es hátizsák időbeli és térbeli komplexitása

• Időbeli komplexitás: O(n · M) — a két beágyazott ciklus n elemet söpör végig M+1 kapacitásállapoton.
• Térbeli komplexitás: O(n · M) a teljes táblázathoz, amely kee segítségével O(M)-re redukálhatóping csak az előző sor, amikor tracAz elektronikus visszaküldés nem szükséges.

A futási idő pszeudo-polinom: polinom az M értékében, de exponenciális az M kódolásához használt bitekben. Ezért marad a 0/1 Knapsack NP-nehéz, annak ellenére, hogy a dinamikus programozás a gyakorlatban hatékony.

A 0/1 hátizsák probléma alkalmazásai

• Rakomány rakodása, konténercsomagolás és raktári komissiózás súlykorlátok alatt.
• Költségvetés elosztása fix költségű és várható megtérülésű beruházási projektek között.
• Forgácsolási problémák a gyártásban, amelyek miatt nem lehet az egyes darabokat szétválasztani.
• Kriptográfiai sémák, mint például a Merkle-Hellman, amelyek a hátizsák keménységére építenek.
• Erőforrás-korlátos ütemezés a felhőalapú számítástechnikában és a CPU-feladatok elhelyezése.
• Funkciókiválasztás gépi tanulásban fix funkcióköltségvetés mellett.

GYIK