streamalism.org

1. Uvod

Problem s naprtnjačom je kombinacijski problem optimizacije koji ima mnogo primjena. U ovom uputstvu taj ćemo problem riješiti na Javi.

2. Problem s naprtnjačom

U problemu s naprtnjačom imamo niz predmeta. Svaka stvar ima težinu i vrijednu vrijednost:

Te predmete želimo staviti u naprtnjaču. Međutim, ima ograničenje težine:

Stoga trebamo odabrati predmete čija ukupna težina ne prelazi ograničenje težine, a njihova ukupna vrijednost je što veća. Na primjer, najbolje rješenje za gornji primjer je odabir predmeta od 5 kg i predmeta od 6 kg, što daje maksimalnu vrijednost od 40 USD unutar ograničenja težine.

Problem s naprtnjačom ima nekoliko varijacija. U ovom uputstvu usredotočit ćemo se na problem s naprtnjačama 0-1. U problemu s naprtnjačom 0-1, svaki predmet mora biti izabran ili ostavljen. Ne možemo uzeti djelomični iznos predmeta. Također, ne možemo uzeti predmet više puta.

3. Matematička definicija

Ajmo sada formalizirati problem 0-1 naprtnjače u matematičke zapise. S obzirom na skup n predmeta i ograničenje težine W, problem optimizacije možemo definirati kao:

Ovaj je problem NP-tvrd. Stoga trenutno ne postoji algoritam polinomnog vremena koji bi ga mogao riješiti. Međutim, postoji pseudo-polinomni algoritam vremena koji koristi dinamičko programiranje za ovaj problem.

4. Rekurzivno rješenje

Za rješavanje ovog problema možemo se poslužiti formulom rekurzije:

U ovoj formuli, M (n, š) je optimalno rješenje za n predmeta s ograničenjem težine w. To je maksimum od sljedeće dvije vrijednosti:

• Optimalno rješenje od (n-1) predmeta s ograničenjem težine w (isključujući n-ti predmet)
• Vrijednost n-ti predmet plus optimalno rješenje od (n-1) predmeta i w minus težina n-ta stavka (uključujući n-ti predmet)

Ako je težina n-ti je predmet veći od trenutne težine, mi ga ne uključujemo. Stoga je u prvoj kategoriji od gore navedena dva slučaja.

Ovu formulu rekurzije možemo implementirati u Javi:

int knapsackRec (int [] w, int [] v, int n, int W) {if (n W) {return knapsackRec (w, v, n - 1, W); } else {povratak Math.max (knapsackRec (w, v, n - 1, W), v [n - 1] + knapsackRec (w, v, n - 1, W - w [n - 1])); }} 

U svakom koraku rekurzije moramo procijeniti dva neoptimalna rješenja. Stoga je vrijeme izvođenja ovog rekurzivnog rješenja O (2n).

5. Rješenje za dinamičko programiranje

Dinamičko programiranje strategija je za lineariziranje inače eksponencijalno teških programskih problema. Ideja je pohraniti rezultate potproblema tako da ih kasnije ne moramo ponovno izračunavati.

Također možemo dinamičkim programiranjem riješiti problem s naprtnjačom 0-1. Da bismo koristili dinamičko programiranje, prvo kreiramo dvodimenzionalnu tablicu s dimenzijama od 0 do n i 0 do W. Zatim koristimo pristup odozdo prema gore za izračunavanje optimalnog rješenja s ovom tablicom:

int knapsackDP (int [] w, int [] v, int n, int W) {if (n <= 0 || W <= 0) {return 0; } int [] [] m = novi int [n + 1] [W + 1]; za (int j = 0; j <= W; j ++) {m [0] [j] = 0; } za (int i = 1; i <= n; i ++) {za (int j = 1; j j) {m [i] [j] = m [i - 1] [j]; } else {m [i] [j] = Math.max (m [i - 1] [j], m [i - 1] [j - w [i - 1]] + v [i - 1]); }}} povratak m [n] [W]; } 

U ovom rješenju imamo ugniježđenu petlju preko broja stavke n i ograničenje težine W. Stoga je vrijeme izvođenja O (nW).

6. Zaključak

U ovom uputstvu pokazali smo matematičku definiciju problema s naprtnjačama 0-1. Tada smo pružili rekurzivno rješenje ovog problema s implementacijom Jave. Napokon, za rješavanje ovog problema koristili smo dinamičko programiranje.

Kao i uvijek, izvorni kôd članka dostupan je na GitHubu.