0/1 Reppu-ongelman korjaus dynaamisen ohjelmoinnin esimerkillä

Mikä on selkäreppu-ongelma?

Reppu ongelma on klassinen kombinatorinen optimointiongelma. Supermarketti myy n paketit (n ≤ 100). Paketti i jonka paino W[i] ≤ 100 ja arvo V[i] ≤ 100. Varas ei voi kantaa yli kapasiteetin M (M ≤ 100). Mitä paketteja varkaan tulisi ottaa ottaakseen maksimaalisen kokonaisarvon?

input:

• Enimmäispaino M ja pakkausten lukumäärä n.
• Joukko painon W[i] ja vastaavan arvon V[i].

lähtö:

• Kapasiteetin rajoissa saavutettavissa oleva suurin kokonaisarvo.
• Tarkka pakkauserä, joka varkaan tulisi ottaa.

Knapsack-algoritmi jakautuu kahteen tunnettuun varianttiin:

• 0/1 Reppuongelma ratkaistu dynaamisella ohjelmoinnilla. Jokainen paketti joko otetaan kokonaisena tai jätetään jäljelle – ei murto-osia eikä kaksoiskappaleita.
• Murtoreppu-ongelma ratkaista ahneella strategialla. Tässä voit ottaa osan mistä tahansa paketista täyttääksesi jäljellä olevan kapasiteetin.

Reppu-ongelman ratkaiseminen dynaamisen ohjelmoinnin avulla esimerkin avulla

Hajoita ja hallitse -menetelmä jakaa suuren ongelman osaongelmiin ja jatkaa sitten jakamista, kunnes jokainen osaongelma on helppo. Tavallinen rekursio kuitenkin usein ratkaisee saman osaongelman monta kertaa ja tuhlaa työtä.

Knapsack-dynaamisen ohjelmoinnin ydinajatuksena on tallentaa jokainen ratkaistu osaongelma taulukkoon. Toistuvat kutsut lukevat vastauksen uudelleenlaskennan sijaan, mikä muuttaa eksponentiaalisen rekursion polynomiaikaiseksi koodiksi.

Ratkaise reppuongelma dynaamisen ohjelmoinnin avulla

Dynaamisen ohjelmoinnin ratkaisun suunnitteluun tarvitaan neljä vaihetta:

• Ratkaise ensin pienimmät osaongelmat.
• Johda rekursio, joka rakentaa osaongelman vastauksen pienemmistä rekursioista.
• Tallenna osaongelmien vastaukset taulukkoon, joka lasketaan alhaalta ylöspäin käyttäen rekursiivisuutta.
• Kokoa lopullinen vastaus täytetystä taulukosta.

Analysoi 0/1-reppu-ongelma

Optimaalinen arvo riippuu kahdesta toisistaan ​​riippumattomasta tekijästä:

1. Kuinka monta pakettia vielä harkitaan?
2. Repun jäljellä oleva paino mahtuu edelleen.

Koska tavoitefunktio riippuu kahdesta suureesta, vaihtoehtotaulukon on oltava kaksiulotteinen. Olkoon B[i][j] merkitsee maksimiarvoa valittaessa pakettien {1, …, i} joukosta, joiden painoraja on j.

• Lopullinen vastaus on B[n][M], paras kokonaisarvo kaikille n paketille kapasiteetin M alla.
• Valittu kokonaispaino on aina rajoitettu nykyiseen kapasiteettiin: B[i][j] ≤ j.

Esimerkki: jos B[4][10] = 8, paras kokonaispaino neljästä ensimmäisestä paketista alle kapasiteetin 10 on 8. Jotkin näistä neljästä paketista voidaan ohittaa.

Laskekaava B[i][j]

• W[i], V[i] ovat paketin i paino ja arvo, missä i on joukossa {1, …, n}.
• M on repun kantaman enimmäispaino.

Perustapaus yhdellä pakkauksella: jokaisella kapasiteetilla j ≥ W[1]:

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

Yleisessä tapauksessa päätä, sisällytetäänkö paketti i kapasiteettiin j:

• Jos paketti i on ohitettu, B[i][j] on yhtä kuin paras arvo käytettäessä paketteja {1, …, i-1} kapasiteetin j rajoissa:

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

• Jos paketti i on otettava (sallittu vain, kun W[i] ≤ j), B[i][j] on yhtä kuin V[i] plus paras arvo paketeista {1, …, i-1} kapasiteetin j – W[i] puitteissa:

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

Valitse kahdesta ehdokkaasta suurempi.

Dynaamisen ohjelmoinnin perusteet

Kahden tapauksen yhdistäminen antaa täyden toistumisen:

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

Perustapaus on B[0][j] = 0 jokaiselle j, koska nollapakettien arvo on nolla kapasiteetista riippumatta.

Laske vaihtoehtotaulukko

Muodosta B käyttämällä rekursiivisuutta. Kun B on täytetty, sama taulukko ohjaa trace-back, joka rekonstruoi valitut paketit. Taulukossa B on n + 1 riviä ja M + 1 saraketta:

• Rivi 0 on perustapaus, joka on täytetty nollilla.
• Käytä riviä 0 rivin 1 laskemiseen, riviä 1 rivin 2 laskemiseen ja jatka, kunnes rivi n on valmis.

Vaihtoehtotaulukko

Trace

Kun B on valmis, keskity siihen B[n][M], optimaalinen kokonaisarvo kaikille n paketille, joiden kapasiteetti on M.

• If B[n][M] = B[n-1][M], pakettia n ei valittu, joten jatka traclähde B[n-1][M].
• If B[n][M] ≠ B[n-1][M], paketti n valittiin, joten jatka trackohdasta B[n-1][M – W[n]].

Toista, kunnes saavutat taulukon rivin 0.

Algoritmi vaihtoehtotaulukon etsimiseksi valittujen pakettien löytämiseksi

Huomautus: aina kun B[i][j] = B[i-1][j], pakettia i ei ole valittu. Arvo B[n][M] on reppuun pakattavan tavaran optimaalinen kokonaisarvo.

Vaiheet tracvalittujen pakettien kanssa:

• Vaihe 1: Aloita kohdasta i = n, j = M.
• Vaihe 2: Skannaa saraketta j alhaalta ylöspäin, kunnes löydät rivin i, jossa B[i][j] > B[i-1][j]. Merkitse paketti i valituksi: Select[i] = true.
• Vaihe 3: Päivitä j = j – W[i]. Jos j > 0, palaa vaiheeseen 2, muuten siirry vaiheeseen 4.
• Vaihe 4: Tulosta jokainen valittuna merkitty paketti.

Java Code

Seuraavat Java metodi täyttää B[][] alhaalta ylöspäin, tulostaa taulukon tarkastusta varten ja sitten traces valitut paketit.

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

Funktio knapsackDyProg() in Java

Koodin selitys:

1. Varaa taulukko B[][] ja alusta jokainen solu arvoon 0.
2. Täytä B[][] alhaalta ylöspäin käyttämällä edellisen osan rekursiota.
3. Aloita jokainen solu arvolla ”skip package i” B[i-1][j].
4. Jos paketin i valitseminen on mahdollista ja antaa ehdottomasti paremman arvon, ylikirjoita solu.
5. Trace valitut kohteet riviltä n takaisin riville 0.
6. Aina kun paketti n valitaan, vähennä jäljellä olevaa kapasiteettia arvolla W[n-1].

Korjaa huomautus: alkuperäisen koodinpätkän muunneltu parametri M vielä lukiessani B[n][M]Yllä oleva turvallisempi versio käyttää erillistä kohdistinta. j varten trace.

Java ajuri suorittaa algoritmin kahdella toimivalla esimerkillä:

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

Ensimmäisen esimerkin tuloste:

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

Toisen esimerkin tuloste:

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-repun aika-avaruuskompleksisuus

• Ajan monimutkaisuus: O(n · M) — kaksi sisäkkäistä silmukkaa pyyhkäisevät n alkiota M+1 kapasiteettitilan läpi.
• Avaruuden monimutkaisuus: O(n · M) koko taulukolle, pelkistettävä arvoon O(M) kee-lausekkeen avullaping vain edellinen rivi, kun tracsähköistä palautusta ei tarvita.

Suoritusaika on pseudo-polynomi: polynomi M:n arvossa, mutta eksponentiaalinen M:n koodaamiseen käytettyjen bitien määrässä. Siksi 0/1 Knapsack on NP-vaikea, vaikka dynaaminen ohjelmointi on käytännössä tehokasta.

0/1-reppuongelman sovellukset

• Rahdin lastaus, konttien pakkaus ja varastokeräily painorajoitusten rajoissa.
• Budjetin kohdentaminen kiinteiden kustannusten ja odotetun tuoton omaavien investointiprojektien kesken.
• Leikkausvarasto-ongelmat valmistuksessa, joissa yksittäisiä kappaleita ei voida jakaa.
• Kryptografiajärjestelmät, kuten Merkle-Hellman, jotka perustuvat repun kovuuteen.
• Resurssien rajoittama aikataulutus pilvipalveluissa ja suorittimen tehtävien sijoittelu.
• Ominaisuuksien valinta koneoppimisessa kiinteällä ominaisuusbudjetilla.

UKK