Tukaj je nahrbtnik kot posoda ali torba. Recimo, da smo dali nekaj postavk, ki imajo določene uteži ali dobičke. Nekaj ​​predmetov moramo dati v nahrbtnik tako, da skupna vrednost ustvari največji dobiček.

Na primer, teža posode je 20 kg. Artikle moramo izbrati tako, da bo vsota teže artiklov manjša ali enaka teži posode, dobiček pa največji.

Obstajata dve vrsti težav z nahrbtnikom:

• 0/1 problem z nahrbtnikom
• Problem frakcijskega nahrbtnika

O obeh težavah bomo razpravljali eno za drugo. Najprej se bomo seznanili s problemom nahrbtnika 0/1.

Kaj je problem nahrbtnika 0/1?

Težava z nahrbtnikom 0/1 pomeni, da so predmeti v celoti napolnjeni ali da v nahrbtniku ni nobenih predmetov. Na primer, imamo dva predmeta, ki tehtata 2 kg oziroma 3 kg. Če izberemo 2kg artikel, ne moremo izbrati 1kg artikla iz 2kg artikla (artikel ni deljiv); 2kg kos moramo v celoti pobrati. To je problem z nahrbtnikom 0/1, pri katerem izberemo predmet v celoti ali pa ga izberemo. Problem nahrbtnika 0/1 je rešen z dinamičnim programiranjem.

Kaj je problem frakcijskega nahrbtnika?

Problem delnega nahrbtnika pomeni, da lahko predmet razdelimo. Na primer, imamo artikel 3 kg, potem lahko izberemo artikel 2 kg in pustimo artikel 1 kg. Problem frakcijskega nahrbtnika je rešen s pristopom Greedy.

Primer problema z nahrbtnikom 0/1.

Razmislite o težavi z utežmi in dobički:

Uteži: {3, 4, 6, 5}

Dobički: {2, 3, 1, 4}

Teža nahrbtnika je 8 kg

Število predmetov je 4

Zgornji problem je mogoče rešiti z naslednjo metodo:

x_jaz= {1, 0, 0, 1}

= {0, 0, 0, 1}

kako pretvoriti celo število v niz java

= {0, 1, 0, 1}

Zgoraj so možne kombinacije. 1 pomeni, da je predmet v celoti izbran, 0 pa, da ni izbran noben element. Ker so predmeti 4, bodo možne kombinacije:

2⁴= 16; torej. Obstaja 16 možnih kombinacij, ki jih je mogoče narediti z uporabo zgornjega problema. Ko so vse kombinacije sestavljene, moramo izbrati kombinacijo, ki zagotavlja največji dobiček.

Drug pristop k reševanju problema je pristop dinamičnega programiranja. Pri pristopu dinamičnega programiranja se zapleten problem razdeli na podprobleme, nato najdemo rešitev podproblema in rešitev podproblema se uporabi za iskanje rešitve kompleksnega problema.

Kako se ta problem lahko reši z uporabo pristopa dinamičnega programiranja?

Prvič,

ustvarimo matriko, prikazano spodaj:

V zgornji matriki stolpci predstavljajo težo, tj. 8. Vrstice predstavljajo dobičke in uteži postavk. Tukaj nismo neposredno vzeli teže 8, problem je razdeljen na podprobleme, tj. 0, 1, 2, 3, 4, 5, 6, 7, 8. Rešitev podproblemov bi shranili v celic in odgovor na problem bi bil shranjen v končni celici. Najprej zapišemo uteži v naraščajočem vrstnem redu in dobičke glede na njihove uteži, prikazane spodaj:

notri_jaz= {3, 4, 5, 6}

str_jaz= {2, 3, 4, 1}

Prva vrstica in prvi stolpec bi bila 0, ker ni elementa za w=0

Ko je i=1, je W=1

notri₁= 3; Ker imamo v kompletu samo en predmet s težo 3, vendar je zmogljivost nahrbtnika 1. Predmeta s 3 kg ne moremo napolniti v nahrbtnik s kapaciteto 1 kg, zato dodajte 0 pri M[1][1], kot je prikazano spodaj. :

Ko je i = 1, je W = 2

notri₁= 3; Ker imamo samo en predmet v kompletu s težo 3, vendar je zmogljivost nahrbtnika 2. Predmeta s 3 kg ne moremo napolniti v nahrbtnik s kapaciteto 2 kg, zato dodajte 0 pri M[1][2], kot je prikazano spodaj. :

Ko je i=1, W=3

notri₁= 3; Ker imamo v kompletu le en kos z težo 3 in je tudi teža nahrbtnika 3; zato lahko nahrbtnik napolnimo s predmetom teže 3. Dobiček, ki ustreza teži 3, tj. 2, postavimo na M[1][3], kot je prikazano spodaj:

Ko je i=1, je W = 4

_W1= 3; Ker imamo v kompletu le en kos z težo 3, teža nahrbtnika pa 4; zato lahko nahrbtnik napolnimo s predmetom teže 3. Dobiček, ki ustreza teži 3, tj. 2, postavimo na M[1][4], kot je prikazano spodaj:

Ko je i=1, je W = 5

_W1= 3; Ker imamo v kompletu samo en predmet z težo 3, teža nahrbtnika pa 5; zato lahko nahrbtnik napolnimo s predmetom teže 3. Dobiček, ki ustreza teži 3, tj. 2, postavimo na M[1][5], kot je prikazano spodaj:

Ko je i =1, W=6

_W1= 3; Ker imamo v kompletu samo en predmet z težo 3, teža nahrbtnika pa 6; zato lahko nahrbtnik napolnimo s predmetom teže 3. Dobiček, ki ustreza teži 3, tj. 2, postavimo na M[1][6], kot je prikazano spodaj:

Ko je i=1, je W = 7

_W1= 3; Ker imamo v kompletu le en kos z težo 3, teža nahrbtnika pa 7; zato lahko nahrbtnik napolnimo s predmetom teže 3. Dobiček, ki ustreza teži 3, tj. 2, postavimo na M[1][7], kot je prikazano spodaj:

Ko je i =1, je W =8

_W1= 3; Ker imamo v kompletu le en kos z težo 3, teža nahrbtnika pa 8; zato lahko nahrbtnik napolnimo s predmetom teže 3. Dobiček, ki ustreza teži 3, tj. 2, postavimo na M[1][8], kot je prikazano spodaj:

Zdaj se vrednost 'i' poveča in postane 2.

Ko je i =2, je W = 1

Teža, ki ustreza vrednosti 2, je 4, tj. w₂= 4. Ker imamo v kompletu samo en predmet s težo enako 4, teža nahrbtnika pa je 1. Predmeta z maso 4 ne moremo dati v nahrbtnik, zato dodamo 0 pri M[2][1 ] prikazano kot spodaj:

Ko je i =2, je W = 2

Teža, ki ustreza vrednosti 2, je 4, tj. w₂= 4. Ker imamo v kompletu samo en predmet s težo 4, teža nahrbtnika pa je 2. Predmeta z težo 4 ne moremo dati v nahrbtnik, zato dodamo 0 pri M[2][2 ] prikazano kot spodaj:

Ko je i =2, je W = 3

Teža, ki ustreza vrednosti 2, je 4, tj. w₂= 4. Ker imamo v kompletu dva predmeta z utežmi 3 in 4, teža nahrbtnika pa je 3. Predmet teže 3 lahko damo v nahrbtnik, zato dodamo 2 pri M[2][3] prikazano kot spodaj:

Ko je i =2, je W = 4

Teža, ki ustreza vrednosti 2, je 4, tj. w₂= 4. Ker imamo v kompletu dva predmeta z težo 3 in 4, teža nahrbtnika pa je 4. Predmet z težo 4 lahko damo v nahrbtnik, saj je dobiček, ki ustreza teži 4, večji od predmeta, ki ima težo 3, zato dodamo 3 pri M[2][4], kot je prikazano spodaj:

Ko je i = 2, je W = 5

Teža, ki ustreza vrednosti 2, je 4, tj. w₂= 4. Ker imamo v kompletu dva predmeta z utežmi 3 in 4, teža nahrbtnika pa je 5. Predmet z težo 4 lahko damo v nahrbtnik in dobiček, ki ustreza teži, je 3, zato dodamo 3 pri M[2][5] prikazano kot spodaj:

Ko je i = 2, je W = 6

Teža, ki ustreza vrednosti 2, je 4, tj. w₂= 4. Ker imamo v kompletu dva predmeta z utežmi 3 in 4, teža nahrbtnika pa je 6. Predmet z težo 4 lahko damo v nahrbtnik in dobiček, ki ustreza teži, je 3, zato dodamo 3 pri M[2][6] prikazano spodaj:

Ko je i = 2, je W = 7

Teža, ki ustreza vrednosti 2, je 4, tj. w₂= 4. Ker imamo v kompletu dva predmeta z utežmi 3 in 4, teža nahrbtnika pa je 7. Predmet z maso 4 in 3 lahko damo v nahrbtnik in dobitka, ki ustrezata uteži, sta 2 in 3; zato je skupni dobiček 5, zato dodamo 5 pri M[2][7], kot je prikazano spodaj:

Ko je i = 2, je W = 8

Teža, ki ustreza vrednosti 2, je 4, tj. w₂= 4. Ker imamo v kompletu dva predmeta z utežmi 3 in 4, teža nahrbtnika pa je 7. Predmet z maso 4 in 3 lahko damo v nahrbtnik in dobitka, ki ustrezata uteži, sta 2 in 3; zato je skupni dobiček 5, zato dodamo 5 pri M[2][7], kot je prikazano spodaj:

Zdaj se vrednost 'i' poveča in postane 3.

Ko je i = 3, je W = 1

indeks jave

Teža, ki ustreza vrednosti 3, je 5, tj. w₃= 5. Ker imamo v nizu tri predmete z utežmi 3, 4 in 5, teža nahrbtnika pa je 1. Nobenega od predmetov ne moremo dati v nahrbtnik, zato dodamo 0 pri M[3][ 1] prikazano kot spodaj:

Ko je i = 3, je W = 2

Teža, ki ustreza vrednosti 3, je 5, tj. w₃= 5. Ker imamo v kompletu tri predmete z težo 3, 4 in 5, teža nahrbtnika pa je 1. Nobenega od predmetov ne moremo dati v nahrbtnik, zato dodamo 0 pri M[3][ 2] prikazano kot spodaj:

Ko je i = 3, je W = 3

Teža, ki ustreza vrednosti 3, je 5, tj. w₃= 5. Ker imamo v nizu tri predmete z težo 3, 4 in 5 in je teža nahrbtnika 3. Predmet s težo 3 lahko damo v nahrbtnik in dobiček, ki ustreza predmetu, je 2, zato dodamo 2 pri M[3][3], kot je prikazano spodaj:

Ko je i = 3, je W = 4

Teža, ki ustreza vrednosti 3, je 5, tj. w₃= 5. Ker imamo v nizu tri predmete teže 3, 4 in 5, teža nahrbtnika pa je 4. Lahko obdržimo predmet teže 3 ali 4; dobiček (3), ki ustreza uteži 4, je večji od dobička, ki ustreza uteži 3, zato dodamo 3 pri M[3][4], kot je prikazano spodaj:

Ko je i = 3, je W = 5

Teža, ki ustreza vrednosti 3, je 5, tj. w₃= 5. Ker imamo v nizu tri predmete teže 3, 4 in 5, teža nahrbtnika pa je 5. Lahko obdržimo predmet bodisi teže 3, 4 ali 5; dobiček (3), ki ustreza uteži 4, je večji od dobička, ki ustreza uteži 3 in 5, zato dodamo 3 pri M[3][5], kot je prikazano spodaj:

Ko je i =3, je W = 6

Teža, ki ustreza vrednosti 3, je 5, tj. w₃= 5. Ker imamo v nizu tri predmete teže 3, 4 in 5, teža nahrbtnika pa je 6. Lahko obdržimo predmet bodisi teže 3, 4 ali 5; dobiček (3), ki ustreza uteži 4, je večji od dobička, ki ustreza uteži 3 in 5, zato dodamo 3 pri M[3][6], kot je prikazano spodaj:

Ko je i =3, je W = 7

Teža, ki ustreza vrednosti 3, je 5, tj. w₃= 5. Ker imamo v nizu tri predmete teže 3, 4 in 5, teža nahrbtnika pa je 7. V tem primeru lahko obdržimo oba predmeta teže 3 in 4, je vsota dobička bi bilo enako (2 + 3), tj. 5, zato dodamo 5 pri M[3][7], kot je prikazano spodaj:

Ko je i = 3, je W = 8

Teža, ki ustreza vrednosti 3, je 5, tj. w₃= 5. Ker imamo v nizu tri predmete teže 3, 4 in 5, teža nahrbtnika pa je 8. V tem primeru lahko obdržimo oba predmeta teže 3 in 4, je vsota dobiček bi bil enak (2 + 3), tj. 5, zato dodamo 5 pri M[3][8], kot je prikazano spodaj:

Zdaj se vrednost 'i' poveča in postane 4.

Ko je i = 4, je W = 1

Teža, ki ustreza vrednosti 4, je 6, tj₄= 6. Ker imamo v nizu štiri predmete z utežmi 3, 4, 5 in 6, teža nahrbtnika pa je 1. Teža vseh predmetov je večja od teže nahrbtnika, zato ne moremo dodate kateri koli predmet v nahrbtnik; Zato dodamo 0 pri M[4][1], kot je prikazano spodaj:

Ko je i = 4, je W = 2

Teža, ki ustreza vrednosti 4, je 6, tj₄= 6. Ker imamo v nizu štiri predmete z utežmi 3, 4, 5 in 6, teža nahrbtnika pa je 2. Teža vseh predmetov je večja od teže nahrbtnika, zato ne moremo dodate kateri koli predmet v nahrbtnik; Zato dodamo 0 pri M[4][2], kot je prikazano spodaj:

Ko je i = 4, je W = 3

Teža, ki ustreza vrednosti 4, je 6, tj₄= 6. Ker imamo v nizu štiri predmete z utežmi 3, 4, 5 in 6, teža nahrbtnika pa je 3. Predmet s težo 3 lahko damo v nahrbtnik in dobiček, ki ustreza utež 4 je 2, zato bomo dodali 2 pri M[4][3], kot je prikazano spodaj:

Ko je i = 4, je W = 4

Teža, ki ustreza vrednosti 4, je 6, tj₄= 6. Ker imamo v nizu štiri predmete z utežmi 3, 4, 5 in 6, teža nahrbtnika pa je 4. Predmet s težo 4 lahko damo v nahrbtnik in dobiček, ki ustreza utež 4 je 3, zato bomo dodali 3 pri M[4][4], kot je prikazano spodaj:

Ko je i = 4, je W = 5

Teža, ki ustreza vrednosti 4, je 6, tj₄= 6. Ker imamo v nizu štiri predmete z utežmi 3, 4, 5 in 6, teža nahrbtnika pa je 5. Predmet s težo 4 lahko damo v nahrbtnik in dobiček, ki ustreza utež 4 je 3, zato bomo dodali 3 pri M[4][5], kot je prikazano spodaj:

Ko je i = 4, je W = 6

java pretvori niz v int

Teža, ki ustreza vrednosti 4, je 6, tj₄= 6. Ker imamo v nizu štiri predmete z utežmi 3, 4, 5 in 6, teža nahrbtnika pa je 6. V tem primeru lahko v nahrbtnik damo predmete z težo 3, 4 , 5 ali 6, vendar je dobiček, tj. 4, ki ustreza uteži 6, največji med vsemi postavkami; zato dodamo 4 pri M[4][6], kot je prikazano spodaj:

Ko je i = 4, je W = 7

Teža, ki ustreza vrednosti 4, je 6, tj₄= 6. Ker imamo v nizu štiri predmete z utežmi 3, 4, 5 in 6, teža nahrbtnika pa je 7. Tukaj, če dodamo dva predmeta z utežmi 3 in 4, bo to ustvarilo največ dobiček, tj. (2 + 3) je enako 5, zato dodamo 5 pri M[4][7], kot je prikazano spodaj:

Ko je i = 4, je W = 8

Teža, ki ustreza vrednosti 4, je 6, tj₄= 6. Ker imamo v nizu štiri predmete z utežmi 3, 4, 5 in 6, teža nahrbtnika pa je 8. Tukaj, če dodamo dva predmeta z utežmi 3 in 4, bo to proizvedlo največjo dobiček, tj. (2 + 3) je enako 5, zato dodamo 5 pri M[4][8], kot je prikazano spodaj:

Kot lahko opazimo v zgornji tabeli, je 5 največji dobiček med vsemi vnosi. Kazalec kaže na zadnjo vrstico in zadnji stolpec z vrednostjo 5. Zdaj bomo vrednost 5 primerjali s prejšnjo vrstico; če prejšnja vrstica, tj. i = 3, vsebuje enako vrednost 5, se bo kazalec premaknil navzgor. Ker prejšnja vrstica vsebuje vrednost 5, bo kazalec premaknjen navzgor, kot je prikazano v spodnji tabeli:

Spet bomo primerjali vrednost 5 iz zgornje vrstice, tj. i = 2. Ker zgornja vrstica vsebuje vrednost 5, bo kazalec ponovno premaknjen navzgor, kot je prikazano v spodnji tabeli:

Spet bomo primerjali vrednost 5 iz zgornje vrstice, tj. i = 1. Ker zgornja vrstica ne vsebuje iste vrednosti, bomo upoštevali vrstico i=1, utež, ki ustreza vrstici, pa je 4. Zato smo izbrali utež 4 in zavrnili uteži 5 in 6, prikazani spodaj:

x = { 1, 0, 0}

Dobiček, ki ustreza uteži, je 3. Zato je preostali dobiček (5 - 3) enak 2. Zdaj bomo to vrednost 2 primerjali z vrstico i = 2. Ker vrstica (i = 1) vsebuje vrednost 2, ; zato se je kazalec premaknil navzgor, kot je prikazano spodaj:

Spet primerjamo vrednost 2 z zgornjo vrstico, tj. i = 1. Ker vrstica i =0 ne vsebuje vrednosti 2, bo izbrana vrstica i = 1 in prikazana je utež, ki ustreza i = 1, 3. spodaj:

X = {1, 1, 0, 0}

Dobiček, ki ustreza uteži, je 2. Zato je preostali dobiček 0. Vrednost 0 primerjamo z zgornjo vrstico. Ker zgornja vrstica vsebuje vrednost 0, vendar je dobiček, ki ustreza tej vrstici, 0. V tej težavi sta izbrani dve uteži, tj. 3 in 4, da bi povečali dobiček.