Ovdje je naprtnjača poput spremnika ili torbe. Pretpostavimo da smo dali neke stavke koje imaju neke težine ili profite. Moramo staviti neke stavke u naprtnjaču na takav način da ukupna vrijednost proizvodi maksimalan profit.

Na primjer, težina kontejnera je 20 kg. Artikle moramo odabrati na način da zbroj težine artikala bude manji ili jednak težini kontejnera, a zarada maksimalna.

Postoje dvije vrste problema s naprtnjačama:

• 0/1 problem s naprtnjačom
• Problem frakcijskog naprtnjače

Razgovarat ćemo o oba problema jedan po jedan. Prvo ćemo naučiti o problemu naprtnjače 0/1.

Što je problem s naprtnjačom 0/1?

Problem s naprtnjačom 0/1 znači da su predmeti u naprtnjači u potpunosti ili da nema stavki. Na primjer, imamo dva predmeta težine 2 kg, odnosno 3 kg. Ako odaberemo stavku od 2 kg, ne možemo odabrati stavku od 1 kg od stavke od 2 kg (stavka nije djeljiva); artikl od 2 kg moramo odabrati u potpunosti. Ovo je problem s naprtnjačom 0/1 u kojem ili biramo predmet u potpunosti ili ćemo odabrati taj predmet. Problem naprtnjače 0/1 riješen je dinamičkim programiranjem.

Što je problem frakcijskog naprtnjače?

Problem frakcijskog naprtnjače znači da možemo podijeliti predmet. Na primjer, imamo artikl od 3 kg, tada možemo odabrati artikl od 2 kg i ostaviti artikl od 1 kg. Problem s frakcijskim naprtnjačama rješava se Greedyjevim pristupom.

Primjer problema s naprtnjačom 0/1.

Razmotrite problem s utezima i dobiti:

Težina: {3, 4, 6, 5}

Dobit: {2, 3, 1, 4}

Težina ruksaka je 8 kg

Broj predmeta je 4

Gore navedeni problem može se riješiti korištenjem sljedeće metode:

x_i= {1, 0, 0, 1}

= {0, 0, 0, 1}

vrste binarnog stabla

= {0, 1, 0, 1}

Gore su moguće kombinacije. 1 označava da je stavka potpuno odabrana, a 0 znači da stavka nije odabrana. Budući da postoje 4 stavke, moguće kombinacije će biti:

2⁴= 16; Tako. Postoji 16 mogućih kombinacija koje se mogu napraviti pomoću gornjeg problema. Nakon što su sve kombinacije napravljene, moramo odabrati kombinaciju koja daje najveći profit.

Drugi pristup rješavanju problema je pristup dinamičkog programiranja. U pristupu dinamičkog programiranja, komplicirani problem se dijeli na podprobleme, zatim se nalazi rješenje podproblema, a rješenje podproblema će se koristiti za pronalaženje rješenja složenog problema.

Kako se ovaj problem može riješiti korištenjem pristupa dinamičkog programiranja?

Prvi,

stvaramo matricu prikazanu u nastavku:

U gornjoj matrici stupci predstavljaju težinu, tj. 8. Redovi predstavljaju dobit i težine stavki. Ovdje nismo izravno uzeli težinu 8, problem je podijeljen na podprobleme, tj. 0, 1, 2, 3, 4, 5, 6, 7, 8. Rješenje podproblema bilo bi spremljeno u ćelije i odgovor na problem bio bi pohranjen u posljednjoj ćeliji. Prvo pišemo težine uzlaznim redoslijedom, a dobit prema njihovim težinama prikazanim u nastavku:

U_i= {3, 4, 5, 6}

str_i= {2, 3, 4, 1}

Prvi redak i prvi stupac bili bi 0 jer ne postoji stavka za w=0

Kada je i=1, W=1

U₁= 3; Budući da imamo samo jednu stavku u setu koja ima težinu 3, ali je kapacitet naprtnjače 1. Ne možemo napuniti stavku od 3 kg u naprtnjaču kapaciteta 1 kg pa dodajte 0 na M[1][1] prikazano ispod :

Kada je i = 1, W = 2

U₁= 3; Budući da imamo samo jednu stavku u setu koja ima težinu 3, ali je kapacitet naprtnjače 2. Ne možemo napuniti stavku od 3 kg u naprtnjaču kapaciteta 2 kg pa dodajte 0 na M[1][2] prikazano ispod :

Kada je i=1, W=3

U₁= 3; Budući da imamo samo jedan predmet u setu koji ima težinu jednaku 3, a težina naprtnjače je također 3; prema tome, možemo napuniti naprtnjaču predmetom težine jednake 3. Dobit koja odgovara težini 3, tj. 2 stavljamo na M[1][3] prikazano u nastavku:

Kada je i=1, W=4

_W1= 3; Budući da imamo samo jedan predmet u setu koji ima težinu jednaku 3, a težina naprtnjače je 4; prema tome, možemo napuniti naprtnjaču predmetom težine jednake 3. Dobit koja odgovara težini 3, tj. 2 stavljamo na M[1][4] prikazano u nastavku:

Kada je i=1, W=5

_W1= 3; Budući da imamo samo jedan predmet u setu koji ima težinu jednaku 3, a težina naprtnjače je 5; prema tome, možemo napuniti naprtnjaču predmetom težine jednake 3. Stavljamo dobit koja odgovara težini 3, tj. 2 na M[1][5] prikazano u nastavku:

Kada je i =1, W=6

_W1= 3; Budući da imamo samo jedan predmet u setu koji ima težinu jednaku 3, a težina naprtnjače je 6; prema tome, možemo napuniti naprtnjaču predmetom težine jednake 3. Dobit koja odgovara težini 3, tj. 2 stavljamo na M[1][6] prikazano u nastavku:

Kada je i=1, W = 7

_W1= 3; Budući da imamo samo jedan predmet u setu koji ima težinu jednaku 3, a težina naprtnjače je 7; prema tome, možemo napuniti naprtnjaču predmetom težine jednake 3. Stavljamo dobit koja odgovara težini 3, tj. 2 na M[1][7] prikazano u nastavku:

Kada je i =1, W =8

_W1= 3; Budući da imamo samo jedan predmet u setu koji ima težinu jednaku 3, a težina naprtnjače je 8; prema tome, možemo napuniti naprtnjaču predmetom težine jednake 3. Dobit koja odgovara težini 3, tj. 2 stavljamo na M[1][8] prikazano u nastavku:

Sada se vrijednost 'i' povećava i postaje 2.

Kada je i =2, W = 1

Težina koja odgovara vrijednosti 2 je 4, tj. w₂= 4. Budući da u setu imamo samo jedan predmet težine 4, a težina ruksaka je 1. Predmet težine 4 ne možemo staviti u ruksak, pa dodajemo 0 na M[2][1 ] prikazano u nastavku:

Kada je i =2, W = 2

Težina koja odgovara vrijednosti 2 je 4, tj. w₂= 4. Budući da u setu imamo samo jedan predmet težine 4, a težina ruksaka je 2. Predmet težine 4 ne možemo staviti u ruksak, pa dodajemo 0 na M[2][2 ] prikazano u nastavku:

Kada je i =2, W = 3

Težina koja odgovara vrijednosti 2 je 4, tj. w₂= 4. Budući da u setu imamo dva predmeta težine 3 i 4, a težina naprtnjače je 3. Predmet težine 3 možemo staviti u naprtnjaču, pa dodajemo 2 na M[2][3] prikazano kao ispod:

Kada je i =2, W = 4

Težina koja odgovara vrijednosti 2 je 4, tj. w₂= 4. Budući da u setu imamo dva predmeta težine 3 i 4, a težina naprtnjače je 4. Predmet težine 4 možemo staviti u naprtnjaču jer je dobit koja odgovara težini 4 veća od težine predmeta 3, pa dodajemo 3 na M[2][4] kako je prikazano u nastavku:

Kada je i = 2, W = 5

Težina koja odgovara vrijednosti 2 je 4, tj. w₂= 4. Budući da imamo dva predmeta u setu s težinama 3 i 4, a težina naprtnjače je 5. Možemo staviti stavku težine 4 u naprtnjaču i dobitak koji odgovara težini je 3, pa dodajemo 3 na M[2][5] prikazano u nastavku:

Kada je i = 2, W = 6

Težina koja odgovara vrijednosti 2 je 4, tj. w₂= 4. Budući da u setu imamo dva predmeta težine 3 i 4, a težina naprtnjače je 6. Predmet težine 4 možemo staviti u naprtnjaču i dobitak koji odgovara težini je 3, pa dodajemo 3 na M[2][6] prikazano u nastavku:

Kada je i = 2, W = 7

Težina koja odgovara vrijednosti 2 je 4, tj. w₂= 4. Budući da u setu imamo dva predmeta težine 3 i 4, a težina naprtnjače je 7. Predmet težine 4 i 3 možemo staviti u naprtnjaču i dobici koji odgovaraju težinama su 2 i 3; prema tome, ukupna dobit je 5, pa dodajemo 5 na M[2][7] prikazano u nastavku:

Kada je i = 2, W = 8

Težina koja odgovara vrijednosti 2 je 4, tj. w₂= 4. Budući da u setu imamo dva predmeta težine 3 i 4, a težina naprtnjače je 7. Predmet težine 4 i 3 možemo staviti u naprtnjaču i dobici koji odgovaraju težinama su 2 i 3; prema tome, ukupna dobit je 5, pa dodajemo 5 na M[2][7] prikazano u nastavku:

Sada se vrijednost 'i' povećava i postaje 3.

Kada je i = 3, W = 1

java petlje

Težina koja odgovara vrijednosti 3 je 5, tj. w₃= 5. Budući da imamo tri predmeta u setu s težinama 3, 4 i 5, a težina naprtnjače je 1. Ne možemo staviti niti jedan predmet u naprtnjaču, pa dodajemo 0 na M[3][ 1] prikazano u nastavku:

Kada je i = 3, W = 2

Težina koja odgovara vrijednosti 3 je 5, tj. w₃= 5. Budući da u setu imamo tri predmeta s težinom 3, 4 i 5, a težina naprtnjače je 1. Ne možemo niti jednu naprtnjaču staviti u naprtnjaču, pa dodajemo 0 na M[3][ 2] prikazano u nastavku:

Kada je i = 3, W = 3

Težina koja odgovara vrijednosti 3 je 5, tj. w₃= 5. Budući da u skupu imamo tri predmeta težine 3, 4 i 5, a težina naprtnjače je 3. Predmet s težinom 3 može se staviti u naprtnjaču, a dobit koja odgovara predmetu je 2, tako da dodajemo 2 na M[3][3] kako je prikazano u nastavku:

Kada je i = 3, W = 4

Težina koja odgovara vrijednosti 3 je 5, tj. w₃= 5. Budući da u skupu imamo tri predmeta težine 3, 4 i 5, a težina naprtnjače je 4. Možemo zadržati predmet težine 3 ili 4; dobit (3) koja odgovara ponderu 4 veća je od dobiti koja odgovara ponderu 3, pa dodajemo 3 na M[3][4] prikazano u nastavku:

Kada je i = 3, W = 5

Težina koja odgovara vrijednosti 3 je 5, tj. w₃= 5. Budući da u skupu imamo tri predmeta težine 3, 4 i 5, a težina naprtnjače je 5. Možemo zadržati predmet težine 3, 4 ili 5; dobit (3) koja odgovara ponderu 4 veća je od dobiti koja odgovara ponderu 3 i 5, tako da dodajemo 3 na M[3][5] kako je prikazano u nastavku:

Kada je i =3, W = 6

Težina koja odgovara vrijednosti 3 je 5, tj. w₃= 5. Budući da u skupu imamo tri predmeta težine 3, 4 i 5, a težina naprtnjače je 6. Možemo zadržati predmet težine 3, 4 ili 5; profit (3) koji odgovara težini 4 veći je od dobiti koji odgovara težini 3 i 5, tako da dodajemo 3 na M[3][6] prikazano u nastavku:

Kada je i =3, W = 7

Težina koja odgovara vrijednosti 3 je 5, tj. w₃= 5. Budući da u skupu imamo tri predmeta težine 3, 4 i 5, a težina naprtnjače je 7. U ovom slučaju, možemo zadržati obje stavke težine 3 i 4, zbroj dobiti bilo bi jednako (2 + 3), tj. 5, tako da dodajemo 5 na M[3][7] prikazano u nastavku:

Kada je i = 3, W = 8

amrita rao glumica

Težina koja odgovara vrijednosti 3 je 5, tj. w₃= 5. Budući da u skupu imamo tri predmeta težine 3, 4 i 5, a težina naprtnjače je 8. U ovom slučaju, možemo zadržati obje stavke težine 3 i 4, zbroj dobit bi bila jednaka (2 + 3), tj. 5, pa dodajemo 5 na M[3][8] prikazano u nastavku:

Sada se vrijednost 'i' povećava i postaje 4.

Kada je i = 4, W = 1

Težina koja odgovara vrijednosti 4 je 6, tj. w₄= 6. Budući da imamo četiri predmeta u skupu težine 3, 4, 5 i 6 redom, a težina naprtnjače je 1. Težina svih predmeta je veća od težine naprtnjače, pa ne možemo dodajte bilo koji predmet u naprtnjaču; Stoga dodajemo 0 na M[4][1] prikazano kao ispod:

Kada je i = 4, W = 2

Težina koja odgovara vrijednosti 4 je 6, tj. w₄= 6. Budući da imamo četiri predmeta u skupu težine 3, 4, 5 i 6 redom, a težina naprtnjače je 2. Težina svih predmeta veća je od težine naprtnjače, pa ne možemo dodajte bilo koji predmet u naprtnjaču; Stoga dodajemo 0 na M[4][2] prikazano kao ispod:

Kada je i = 4, W = 3

Težina koja odgovara vrijednosti 4 je 6, tj. w₄= 6. Budući da imamo četiri predmeta u skupu težine 3, 4, 5 i 6 redom, a težina naprtnjače je 3. Predmet s težinom 3 može se staviti u naprtnjaču i dobit odgovara težina 4 je 2, pa ćemo dodati 2 na M[4][3] kako je prikazano u nastavku:

Kada je i = 4, W = 4

Težina koja odgovara vrijednosti 4 je 6, tj. w₄= 6. Budući da imamo četiri predmeta u skupu težine 3, 4, 5 i 6 redom, a težina naprtnjače je 4. Predmet s težinom 4 može se staviti u naprtnjaču i dobit koja odgovara težina 4 je 3, pa ćemo dodati 3 na M[4][4] kako je prikazano u nastavku:

Kada je i = 4, W = 5

Težina koja odgovara vrijednosti 4 je 6, tj. w₄= 6. Budući da imamo četiri predmeta u skupu težine 3, 4, 5 i 6 redom, a težina naprtnjače je 5. Predmet s težinom 4 može se staviti u naprtnjaču i dobit odgovara težina 4 je 3, tako da ćemo dodati 3 na M[4][5] prikazano u nastavku:

Kada je i = 4, W = 6

Težina koja odgovara vrijednosti 4 je 6, tj. w₄= 6. Budući da imamo četiri predmeta u skupu težine 3, 4, 5 i 6, a težina naprtnjače je 6. U ovom slučaju, možemo staviti predmete u naprtnjaču bilo koje težine 3, 4 , 5 ili 6, ali je dobit, tj. 4 koja odgovara težini 6, najveća među svim stavkama; stoga, dodajemo 4 na M[4][6] prikazano kao ispod:

Kada je i = 4, W = 7

Težina koja odgovara vrijednosti 4 je 6, tj. w₄= 6. Budući da imamo četiri predmeta u skupu težine 3, 4, 5 i 6 redom, a težina naprtnjače je 7. Ovdje, ako zbrojimo dva predmeta težine 3 i 4, to će proizvesti maksimum profit, tj. (2 + 3) jednako je 5, tako da dodajemo 5 na M[4][7] prikazano u nastavku:

Kada je i = 4, W = 8

Težina koja odgovara vrijednosti 4 je 6, tj. w₄= 6. Budući da imamo četiri predmeta u skupu težine 3, 4, 5 i 6 redom, a težina naprtnjače je 8. Ovdje, ako zbrojimo dva predmeta težine 3 i 4 tada će proizvesti maksimum profit, tj. (2 + 3) jednako je 5, tako da dodajemo 5 na M[4][8] prikazano u nastavku:

Kao što možemo vidjeti u gornjoj tablici, 5 je najveći profit među svim unosima. Pokazivač pokazuje na zadnji redak i zadnji stupac koji imaju vrijednost 5. Sada ćemo usporediti vrijednost 5 s prethodnim redom; ako prethodni red, tj. i = 3 sadrži istu vrijednost 5 tada će se pokazivač pomaknuti prema gore. Budući da prethodni red sadrži vrijednost 5, pokazivač će biti pomaknut prema gore kao što je prikazano u donjoj tablici:

Ponovno ćemo usporediti vrijednost 5 iz gornjeg retka, tj. i = 2. Budući da gornji red sadrži vrijednost 5, pokazivač će ponovno biti pomaknut prema gore kao što je prikazano u donjoj tablici:

Opet ćemo usporediti vrijednost 5 iz gornjeg retka, tj. i = 1. Budući da gornji red ne sadrži istu vrijednost, razmotrit ćemo redak i=1, a težina koja odgovara retku je 4. Stoga , odabrali smo težinu 4 i odbacili smo težine 5 i 6 prikazane u nastavku:

x = { 1, 0, 0}

Dobit koja odgovara ponderu je 3. Prema tome, preostali profit je (5 - 3) jednak 2. Sada ćemo usporediti ovu vrijednost 2 s redom i = 2. Budući da red (i = 1) sadrži vrijednost 2 ; stoga je pokazivač pomaknut prema gore prikazano u nastavku:

Ponovno uspoređujemo vrijednost 2 s gornjim redom, tj. i = 1. Budući da redak i =0 ne sadrži vrijednost 2, bit će odabran redak i = 1 i prikazana je težina koja odgovara i = 1. ispod:

X = {1, 1, 0, 0}

Dobit koja odgovara težini je 2. Stoga je preostala dobit 0. Uspoređujemo vrijednost 0 s gornjim redom. Budući da gornji redak sadrži vrijednost 0, ali dobit koja odgovara ovom retku je 0. U ovom problemu odabrane su dvije težine, tj. 3 i 4 kako bi se maksimizirala dobit.