Tässä reppu on kuin kontti tai laukku. Oletetaan, että olemme antaneet joitakin kohteita, joilla on painoarvoa tai voittoa. Meidän on laitettava joitain esineitä reppuun siten, että kokonaisarvo tuottaa suurimman voiton.

Esimerkiksi säiliön paino on 20 kg. Tuotteet on valittava siten, että tavaroiden painojen summa on joko pienempi tai yhtä suuri kuin kontin paino ja voitto maksimi.

Reppuongelmia on kahdenlaisia:

• 0/1 reppu-ongelma
• Murtoreppu-ongelma

Keskustelemme molemmista ongelmista yksitellen. Ensin opimme 0/1-reppu-ongelmasta.

Mikä on 0/1-reppu-ongelma?

0/1 reppuongelma tarkoittaa, että tuotteet ovat joko kokonaan tai niitä ei ole täytetty repussa. Meillä on esimerkiksi kaksi tuotetta, joiden paino on 2 kg ja 3 kg. Jos valitsemme 2 kg:n tuotteen, emme voi valita 1 kg:n tuotetta 2 kg:n tuotteista (tuote ei ole jaettavissa); meidän on valittava 2kg tuote kokonaan. Tämä on 0/1-reppuongelma, jossa joko valitsemme tuotteen kokonaan tai valitsemme sen. 0/1-reppuongelma ratkaistaan ​​dynaamisen ohjelmoinnin avulla.

Mikä on murtoreppu-ongelma?

Murto-reppu-ongelma tarkoittaa, että voimme jakaa esineen. Esimerkiksi meillä on 3 kg:n tuote, jonka jälkeen voimme valita 2 kg:n tuotteen ja jättää 1 kg:n tavaran. Murtoreppu-ongelma ratkaistaan ​​ahneella lähestymistavalla.

Esimerkki 0/1-reppuongelmasta.

Harkitse ongelmaa, jossa painot ja voitot ovat:

Painot: {3, 4, 6, 5}

Voitot: {2, 3, 1, 4}

Reppun paino on 8 kg

Kohteiden lukumäärä on 4

Yllä oleva ongelma voidaan ratkaista käyttämällä seuraavaa menetelmää:

x_i= {1, 0, 0, 1}

= {0, 0, 0, 1}

täysi lomake

= {0, 1, 0, 1}

Yllä olevat ovat mahdollisia yhdistelmiä. 1 tarkoittaa, että tuote on poimittu kokonaan ja 0 tarkoittaa, että tuotetta ei ole poimittu. Koska kohteita on 4, mahdolliset yhdistelmät ovat:

2⁴= 16; Niin. Yllä olevaa ongelmaa käyttämällä voidaan tehdä 16 mahdollista yhdistelmää. Kun kaikki yhdistelmät on tehty, meidän on valittava yhdistelmä, joka tarjoaa suurimman voiton.

Toinen tapa ratkaista ongelma on dynaaminen ohjelmointi lähestymistapa. Dynaamisessa ohjelmoinnin lähestymistavassa monimutkainen ongelma jaetaan osaongelmiin, sitten löydetään osaongelman ratkaisu ja aliongelman ratkaisua käytetään monimutkaisen ongelman ratkaisun löytämiseen.

Kuinka tämä ongelma voidaan ratkaista käyttämällä dynaamisen ohjelmoinnin lähestymistapaa?

Ensimmäinen,

luomme alla olevan matriisin:

Yllä olevassa matriisissa sarakkeet edustavat painoa, eli 8. Rivit edustavat tuotteiden voittoja ja painoja. Tässä emme ole ottaneet painoa 8 suoraan, tehtävä on jaettu osatehtäviin, eli 0, 1, 2, 3, 4, 5, 6, 7, 8. Osatehtävien ratkaisu tallennettaisiin solut ja vastaus ongelmaan tallennettaisiin viimeiseen soluun. Ensin kirjoitamme painot nousevaan järjestykseen ja voitot niiden painojen mukaan seuraavasti:

Sisään_i= {3, 4, 5, 6}

s_i= {2, 3, 4, 1}

Ensimmäinen rivi ja ensimmäinen sarake olisivat 0, koska w=0:lle ei ole kohdetta

Kun i=1, W=1

Sisään₁= 3; Koska meillä on sarjassa vain yksi esine, jonka paino on 3, mutta repun kapasiteetti on 1. Emme voi täyttää 3 kg:n tuotetta 1 kg:n reppussa, joten lisää 0 kohtaan M[1][1], kuten alla :

Kun i = 1, W = 2

Sisään₁= 3; Koska sarjassa on vain yksi esine, jonka paino on 3, mutta repun kapasiteetti on 2. Emme voi täyttää 3 kg:n tuotetta 2 kg:n reppussa, joten lisää 0 kohtaan M[1][2], kuten alla :

Kun i = 1, W = 3

Sisään₁= 3; Koska sarjassa on vain yksi esine, jonka paino on 3, ja repun paino on myös 3; siksi voimme täyttää reppun painolla, joka on yhtä suuri kuin 3. Laitamme painoa 3 vastaavan voiton, eli 2 kohdassa M[1][3], kuten alla:

Kun i = 1, W = 4

_W1= 3; Koska meillä on sarjassa vain yksi esine, jonka paino on 3, ja repun paino on 4; siksi voimme täyttää reppun tuotteella, jonka paino on 3. Laitamme voiton, joka vastaa painoa 3, eli 2 kohdassa M[1][4] seuraavasti:

Kun i = 1, W = 5

_W1= 3; Koska meillä on sarjassa vain yksi esine, jonka paino on 3, ja repun paino on 5; siksi voimme täyttää reppun painolla, joka on yhtä suuri kuin 3. Laitamme painoa 3 vastaavan voiton, eli 2 kohdassa M[1][5], kuten alla:

Kun i = 1, W = 6

_W1= 3; Koska meillä on sarjassa vain yksi esine, jonka paino on 3, ja repun paino on 6; siksi voimme täyttää reppun tuotteella, jonka paino on 3. Laitamme voittoa vastaavan painon 3, eli 2 kohdassa M[1][6], kuten alla:

Kun i = 1, W = 7

_W1= 3; Koska meillä on sarjassa vain yksi esine, jonka paino on 3, ja repun paino on 7; siksi voimme täyttää reppun tuotteella, jonka paino on 3. Laitamme painoa 3 vastaavan voiton, eli 2 kohdassa M[1][7] seuraavasti:

Kun i = 1, W = 8

_W1= 3; Koska meillä on sarjassa vain yksi esine, jonka paino on 3, ja repun paino on 8; siksi voimme täyttää reppun painolla, joka on yhtä suuri kuin 3. Laitamme painoa 3 vastaavan voiton, eli 2 kohdassa M[1][8], kuten alla:

Nyt i:n arvo kasvaa ja siitä tulee 2.

Kun i = 2, W = 1

Arvoa 2 vastaava paino on 4, eli w₂= 4. Koska joukossa on vain yksi esine, jonka paino on 4, ja repun paino on 1. Emme voi laittaa painoa 4 reppuun, joten lisäämme 0 kohtaan M[2][1 ] alla:

Kun i = 2, W = 2

Arvoa 2 vastaava paino on 4, eli w₂= 4. Koska joukossa on vain yksi esine, jonka paino on 4, ja repun paino on 2. Emme voi laittaa painoa 4 reppuun, joten lisäämme 0 kohtaan M[2][2 ] alla:

Kun i = 2, W = 3

Arvoa 2 vastaava paino on 4, eli w₂= 4. Koska meillä on sarjassa kaksi esinettä painoilla 3 ja 4 ja repun paino on 3. Voimme laittaa painon 3 esineen reppuun, joten lisäämme 2 kohtaan M[2][3] näytetään alla:

Kun i = 2, W = 4

Arvoa 2 vastaava paino on 4, eli w₂= 4. Koska meillä on sarjassa kaksi esinettä painoilla 3 ja 4 ja repun paino on 4. Voimme laittaa painon 4 tavaran reppuun, koska painoa 4 vastaava voitto on suurempi kuin painoinen esine. 3, joten lisäämme 3 kohtaan M[2][4], kuten alla:

Kun i = 2, W = 5

Arvoa 2 vastaava paino on 4, eli w₂= 4. Koska meillä on sarjassa kaksi tuotetta painoilla 3 ja 4 ja repun paino on 5. Voimme laittaa painon 4 tavaran reppuun ja painoa vastaava voitto on 3, joten lisäämme 3 M[2][5] näytetään alla:

Kun i = 2, W = 6

Arvoa 2 vastaava paino on 4, eli w₂= 4. Koska meillä on sarjassa kaksi tuotetta painoilla 3 ja 4 ja repun paino on 6. Voimme laittaa painon 4 tavaran reppuun ja painoa vastaava voitto on 3, joten lisäämme 3 M[2][6] näkyy alla:

Kun i = 2, W = 7

Arvoa 2 vastaava paino on 4, eli w₂= 4. Koska meillä on sarjassa kaksi esinettä painoilla 3 ja 4 ja repun paino on 7. Voimme laittaa painon 4 ja 3 tavarat reppuun ja painoja vastaavat voitot ovat 2 ja 3; siksi kokonaisvoitto on 5, joten lisäämme 5 kohdassa M[2][7], kuten alla:

Kun i = 2, W = 8

Arvoa 2 vastaava paino on 4, eli w₂= 4. Koska meillä on sarjassa kaksi esinettä painoilla 3 ja 4 ja repun paino on 7. Voimme laittaa painon 4 ja 3 tavarat reppuun ja painoja vastaavat voitot ovat 2 ja 3; siksi kokonaisvoitto on 5, joten lisäämme 5 kohdassa M[2][7], kuten alla:

Nyt i:n arvo kasvaa ja siitä tulee 3.

Kun i = 3, W = 1

java pää

Arvoa 3 vastaava paino on 5, eli w₃= 5. Koska meillä on joukossa kolme esinettä, joiden painot ovat 3, 4 ja 5, ja repun paino on 1. Emme voi laittaa kumpaakaan esinettä reppuun, joten lisäämme 0 kohtaan M[3][ 1] alla:

Kun i = 3, W = 2

Arvoa 3 vastaava paino on 5, eli w₃= 5. Koska meillä on joukossa kolme esinettä painoilla 3, 4 ja 5, ja repun paino on 1. Emme voi laittaa kumpaakaan esinettä reppuun, joten lisäämme 0 kohtaan M[3][ 2] alla:

Kun i = 3, W = 3

Arvoa 3 vastaava paino on 5, eli w₃= 5. Koska meillä on kolme tuotetta painojen 3, 4 ja 5 joukossa, ja repun paino on 3. Paino 3:n tavara voidaan laittaa reppuun ja tuotetta vastaava voitto on 2, joten lisäämme 2 kohtaan M[3][3], kuten alla:

Kun i = 3, W = 4

Arvoa 3 vastaava paino on 5, eli w₃= 5. Koska meillä on kolme esinettä painojen 3, 4 ja 5 joukossa, ja repun paino on 4. Voimme pitää tavaran, jonka paino on 3 tai 4; painoa 4 vastaava voitto (3) on suurempi kuin painoa 3 vastaava voitto, joten lisäämme 3 kohdassa M[3][4] seuraavasti:

Kun i = 3, W = 5

Arvoa 3 vastaava paino on 5, eli w₃= 5. Koska meillä on kolme esinettä painojen 3, 4 ja 5 joukossa, ja repun paino on 5. Voimme säilyttää tavaran, jonka paino on 3, 4 tai 5; painoa 4 vastaava voitto (3) on suurempi kuin painoja 3 ja 5 vastaava voitto, joten lisäämme 3 kohdassa M[3][5] seuraavasti:

Kun i = 3, W = 6

Arvoa 3 vastaava paino on 5, eli w₃= 5. Koska meillä on kolme esinettä painojen 3, 4 ja 5 joukossa, ja repun paino on 6. Voimme säilyttää tavaran, jonka paino on 3, 4 tai 5; painoa 4 vastaava voitto (3) on suurempi kuin painoja 3 ja 5 vastaava voitto, joten lisäämme 3 kohdassa M[3][6] seuraavasti:

Kun i = 3, W = 7

Arvoa 3 vastaava paino on 5, eli w₃= 5. Koska meillä on kolme tuotetta painojen joukossa 3, 4 ja 5, ja repun paino on 7. Tässä tapauksessa voimme säilyttää sekä painotuotteet 3 että 4, voiton summa olisi yhtä suuri kuin (2 + 3), eli 5, joten lisäämme 5 kohdassa M[3][7] seuraavasti:

Kun i = 3, W = 8

verilog-tapauslausunto

Arvoa 3 vastaava paino on 5, eli w₃= 5. Koska meillä on kolme esinettä painojen joukossa 3, 4 ja 5, ja repun paino on 8. Tässä tapauksessa voimme säilyttää sekä painotuotteet 3 että 4, summa voitto olisi yhtä suuri kuin (2 + 3), eli 5, joten lisäämme 5 kohdassa M[3][8] seuraavasti:

Nyt i:n arvo kasvaa ja siitä tulee 4.

Kun i = 4, W = 1

Arvoa 4 vastaava paino on 6, eli w₄= 6. Koska meillä on neljä esinettä painojen joukossa 3, 4, 5 ja 6, ja repun paino on 1. Kaikkien esineiden paino on enemmän kuin repun paino, joten emme voi lisää mikä tahansa esine reppuun; Siksi lisäämme 0:n kohtaan M[4][1], kuten alla:

Kun i = 4, W = 2

Arvoa 4 vastaava paino on 6, eli w₄= 6. Koska meillä on neljä esinettä painojen joukossa 3, 4, 5 ja 6, ja repun paino on 2. Kaikkien esineiden paino on enemmän kuin repun paino, joten emme voi lisää mikä tahansa esine reppuun; Siksi lisäämme 0:n kohtaan M[4][2], kuten alla:

Kun i = 4, W = 3

Arvoa 4 vastaava paino on 6, eli w₄= 6. Koska meillä on neljä tuotetta painojen 3, 4, 5 ja 6 joukossa, ja repun paino on 3. Painolla 3 oleva esine voidaan laittaa reppuun ja voitto vastaa reppua. paino 4 on 2, joten lisäämme 2 kohtaan M[4][3], kuten alla:

Kun i = 4, W = 4

Arvoa 4 vastaava paino on 6, eli w₄= 6. Koska meillä on neljä tuotetta painojen 3, 4, 5 ja 6 joukossa, ja repun paino on 4. Painolla 4 oleva esine voidaan laittaa reppuun ja voitto vastaa reppua. paino 4 on 3, joten lisäämme 3 kohtaan M[4][4], kuten alla:

Kun i = 4, W = 5

Arvoa 4 vastaava paino on 6, eli w₄= 6. Koska meillä on neljä esinettä painojen 3, 4, 5 ja 6 joukossa, ja repun paino on 5. Painolla 4 oleva esine voidaan laittaa reppuun ja voitto vastaa reppua. paino 4 on 3, joten lisäämme 3 kohtaan M[4][5], kuten alla:

Kun i = 4, W = 6

Arvoa 4 vastaava paino on 6, eli w₄= 6. Koska meillä on neljä esinettä painojen joukossa 3, 4, 5 ja 6, ja repun paino on 6. Tässä tapauksessa voimme laittaa tavarat reppuun joko painoista 3, 4 , 5 tai 6, mutta voitto, eli painoa 6 vastaava 4 on suurin kaikista eristä; siksi lisäämme 4 kohtaan M[4][6] seuraavasti:

Kun i = 4, W = 7

Arvoa 4 vastaava paino on 6, eli w₄= 6. Koska meillä on neljä esinettä painojen joukossa 3, 4, 5 ja 6, ja repun paino on 7. Tässä, jos lisäämme kaksi painoa 3 ja 4 olevaa esinettä, saadaan maksimi voitto, eli (2 + 3) on 5, joten lisäämme 5 kohdassa M[4][7] seuraavasti:

Kun i = 4, W = 8

Arvoa 4 vastaava paino on 6, eli w₄= 6. Koska meillä on neljä esinettä painojen joukossa 3, 4, 5 ja 6, ja repun paino on 8. Tässä, jos lisäämme kaksi painoa 3 ja 4 olevaa esinettä, saadaan maksimi voitto, eli (2 + 3) on 5, joten lisäämme 5 kohdassa M[4][8] seuraavasti:

Kuten yllä olevasta taulukosta huomaamme, että 5 on suurin voitto kaikkien merkintöjen joukossa. Osoitin osoittaa viimeiseen riviin ja viimeiseen sarakkeeseen, jonka arvo on 5. Nyt vertaamme 5 arvoa edelliseen riviin; jos edellinen rivi eli i = 3 sisältää saman arvon 5, osoitin siirtyy ylöspäin. Koska edellinen rivi sisältää arvon 5, osoitinta siirretään ylöspäin alla olevan taulukon mukaisesti:

Verrataan jälleen yllä olevan rivin arvoa 5, eli i = 2. Koska yllä oleva rivi sisältää arvon 5, osoitinta siirretään jälleen ylöspäin alla olevan taulukon mukaisesti:

Verrataan jälleen yllä olevan rivin arvoa 5, eli i = 1. Koska yllä oleva rivi ei sisällä samaa arvoa, katsomme rivin i=1 ja riviä vastaava paino on 4. , olemme valinneet painon 4 ja hylänneet alla näkyvät painot 5 ja 6:

x = { 1, 0, 0}

Painoa vastaava voitto on 3. Jäljellä oleva voitto on siis (5 - 3) yhtä kuin 2. Nyt verrataan tätä arvoa 2 riviin i = 2. Koska rivi (i = 1) sisältää arvon 2 ; siksi osoitin siirtyi ylöspäin alla olevan kuvan mukaisesti:

Taaskin verrataan arvoa 2 yllä olevaan riviin, eli i = 1. Koska rivi i =0 ei sisällä arvoa 2, niin rivi i = 1 valitaan ja i = 1:tä vastaava paino näytetään 3. alla:

X = {1, 1, 0, 0}

Painoa vastaava voitto on 2. Jäljellä oleva voitto on siis 0. Verrataan 0-arvoa yllä olevaan riviin. Koska yllä oleva rivi sisältää arvon 0, mutta tätä riviä vastaava voitto on 0. Tässä tehtävässä valitaan kaksi painoarvoa, eli 3 ja 4 voiton maksimoimiseksi.