Päivitys: Lue optimoinnista tilaa monimutkaisuus dynaamisen ohjelmoinnin ratkaisu minun artikkelin täällä.,
Repun Ongelma on todella mielenkiintoinen ongelma combinatorics — mainita Wikipedia,
”koska joukko kohteita, joilla kullakin on paino ja arvo, määrittää, kuinka monta kunkin kohteen sisällyttää kokoelma niin, että kokonaispaino on vähemmän kuin tai yhtä suuri kuin annettu raja-arvo ja yhteenlaskettu arvo on mahdollisimman suuri.”
Wikipedia, näemme, että on olemassa muutamia muunnelmia Selkäreppu Ongelma: 0-1 selkäreppu, joka rajoittuu selkäreppu, ja rajaton selkäreppu., Tänään keskitymme yleisimpään (ja yksinkertaisimpaan) variaatioon: 0-1 knapsack-ongelmaan.
hieman enemmän mielenkiintoinen ja relatable muotoili 0-1 selkäreppu ongelma on:
Harkitse varas pääsee kotiin, ryöstää ja hän kantaa laukkunsa. On olemassa kiinteä määrä kohteita kotona — jokaisella on oma paino ja arvo — Koruja, vähemmän painoa ja korkein arvo vs taulukot, joissa on vähemmän arvoa, mutta paljon raskas. Polttoaineen lisäämiseksi tulipaloon varkaalla on vanha reppu, jonka kapasiteetti on rajallinen., Ilmeisesti hän ei voi jakaa pöytää puoleen tai koruja 3 / 4thiin. Hän joko ottaa tai jättää sen. Lähde,
Valitettavasti, minulla oli vaikeuksia ymmärtää joitakin osia Hackerearth artikkeli, joka on, miksi päätin kirjoittaa oman artikkelin. Tämä artikkeli perustuu suurelta osin pois Hackerearth artikkeli ja koodi pätkiä on kirjoitettu Java. Olen tacking ylimääräisiä selityksiä ja selityksiä, missä ne ovat mielestäni tarpeen.
ratkaisemme tämän ongelman dynaamisella ohjelmoinnilla., Dynaaminen ohjelmointi vaatii optimaalinen alusrakenne ja päällekkäisiä sub-ongelmia, jotka molemmat ovat läsnä 0-1 selkäreppu ongelma, kuten tulemme näkemään.
on ihan ok, jos ei ymmärrä, mitä ”optimaaliset alarakenteet” ja ”päällekkäiset alaongelmat” ovat (se on artikkeli toiselle päivälle). Pohjimmiltaan se tarkoittaa vain tiettyä ongelmien makua, jonka avulla voimme käyttää aikaisempia ratkaisuja uudelleen pienempiin ongelmiin, jotta voimme laskea ratkaisun nykyiseen ongelmaan. Näet kohta, mitä tarkoitan.,
ongelma tiedot
koska tämä on 0-1 knapsack ongelma, voimme joko sisällyttää esineen meidän knapsack tai jättää sen, mutta ei sisällyttää murto-osa siitä, tai sisällyttää sen useita kertoja.
Ratkaisu
Ensinnäkin, meidän luo 2-ulotteinen taulukko (eli taulukko) n + 1 rivit ja w + 1 sarakkeet.
rivi numero edustaa joukko kaikki kohteet rivit 1— i. Esimerkiksi arvot rivillä 3 oletetaan, että meillä on vain kohdat 1, 2 ja 3.
kolumni numero j edustaa reppumme painokapasiteettia., Siksi esimerkiksi sarakkeen 5 arvot lähtevät siitä, että reppuumme mahtuu 5 painoyksikköä.
Laitat kaiken yhdessä, merkintä rivi i, sarake j vastaa suurin arvo, joka voidaan saada kohteet 1, 2, 3 … minä, selkäreppu, johon mahtuu j paino yksikköä.
Let ’ s call our table mat for matrix. Siksi int mat = new int.
Vaihe 2:
– Voimme heti aloittaa täyttämällä joitakin merkintöjä meidän pöydän: pohja tapauksissa, joissa ratkaisu on triviaali., Esimerkiksi rivillä 0, kun meillä ei ole kohteita poimia, enimmäisarvo, joka voidaan tallentaa missä tahansa knapsack on 0. Vastaavasti sarakkeessa 0, kun kyseessä on reppu, jossa voi olla 0 painoyksikköä, enimmäisarvo, joka voidaan tallentaa siihen, on 0. (Oletamme, että ei ole massattomia, arvokkaita esineitä.)
Voimme tehdä tämän kanssa 2 silmukoita:
Vaihe 3 (ongelman ydin):
Nyt me haluamme aloittaa asuttavat meidän pöytään., Kuten kaikissa dynaamisissa ohjelmointiratkaisuissa, jokaisessa vaiheessa hyödynnämme ratkaisujamme aiempiin alaongelmiin.
kerron ensin logiikan, ennen kuin esitän konkreettisen esimerkin.
suhde arvo rivi-i, sarake j ja arvot edelliseen osa-ongelmiin seuraavasti:
Muista, että tällä rivillä i ja sarakkeessa j, käsittelemme osa-ongelma, joka koostuu kohteet 1, 2, 3 … en kanssa selkäreppu j kapasiteettia. Tässä vaiheessa on 2 vaihtoehtoa: voimme joko sisällyttää kohtaan I tai ei., Siksi meidän täytyy verrata suurin arvo, että me voimme saada ja ilman kohteen minä.
suurin arvo, että voimme saada ilman kohteen minä löytyy rivi i-1, sarake j. Tämä osa on helppoa. Perustelu on yksinkertainen: mitä maksimiarvo voimme saada kanssa erät 1, 2, 3 … minulla on ilmeisesti sama maksimiarvo voimme saada kanssa erät 1, 2, 3 …, i – 1, jos emme halua sisällyttää kohteen minä.
laskea suurin arvo, että voimme saada tuote minun, meidän täytyy ensin vertailla nimikkeen paino i repun painon kapasiteetti., Tietenkin, jos kohta en painaa enemmän kuin mitä repun voi pitää, emme voi lisätä sitä, joten se ei ole järkevää suorittaa laskennan. Tällöin ratkaisu tähän ongelmaan on yksinkertaisesti maksimiarvo, jonka voimme saada ilman kohtaa i (eli arvo edellä olevassa rivissä, samassa sarakkeessa).
oletetaan kuitenkin, että kohta i painaa vähemmän kuin knapsackin kapasiteetti. Meillä on siis mahdollisuus sisällyttää se, jos se mahdollisesti lisää suurimman mahdollisen arvon., Suurimman mahdollisen arvon, jonka mukaan tuote on siten = arvon kohde minä itse + suurin arvo, joka voidaan saada jäljellä olevan kapasiteetin reppu. Me haluamme tietenkin hyödyntää täysin reppureissumme kapasiteettia, emmekä anna jäljellä olevan kapasiteetin mennä hukkaan.
näin Ollen, rivi i ja sarake j (joka vastaa suurin arvo, että voimme saada siellä), me valita joko suurin arvo, että voimme saada ilman kohteen minä, tai suurin arvo, että voimme saada kohteen minä, sen mukaan, kumpi on suurempi.
tässä konkreettinen esimerkki siitä, mitä tarkoitan.,
Tällä rivillä 3 (kohta 2), ja sarakkeessa 5 (repun kapasiteetti 4), voimme valita joko sisältävät kohta 2 (joka painaa 4 yksikköä) vai ei. Jos emme halua sisällyttää sen suurin arvo voimme saada, on sama kuin jos meillä on vain kohdan 1 valitse (joka löytyy rivi yläpuolelle, eli 0)., Jos haluamme sisältävät kohta 2, suurin arvo, me voimme saada kohde 2 on arvo kohdassa 2 (40) + suurin arvo voimme saada jäljellä olevaa kapasiteettia (joka on 0, sillä repun on aivan täynnä jo).
rivillä 3 (kohta 2) ja sarakkeessa 10 (knapsack kapasiteetti 9), jälleen, voimme valita joko sisällyttää kohteen 2 tai ei. Jos emme halua, enimmäisarvo, jonka voimme saada, on sama kuin edellä olevassa rivissä samassa sarakkeessa, eli 10 (sisällyttämällä vain 1 kohta, jonka arvo on 10). Jos otamme mukaan kohteen 2, meillä on jäljellä knapsack kapasiteetti 9 – 4 = 5., Voimme selvittää maksimiarvon, joka saadaan kapasiteetilla 5 katsomalla edellä olevaa riviä sarakkeesta 5. Näin ollen suurin arvo, jonka voimme saada sisällyttämällä kohteen 2, on 40 (kohteen 2 arvo) + 10 = 50.
haemme suurempi 50 vs 10, joten suurin arvo voimme saada kanssa erät 1 ja 2, jossa on repun kapasiteetti on 9, on 50.,
algoritmi voidaan ilmaista Java, kuten tämä:
Vaihe 4 (lopullinen ratkaisu):
Kun taulukko on täytetty, lopullinen ratkaisu löytyy viimeisen rivin viimeisessä sarakkeessa, joka edustaa suurin arvo on saatavissa kaikki kohteet, ja koko kapasiteetti reppu.
return mat;
Työskentely-koodi:
Huomautus: tässä olen painettu lopullinen vastaus sen sijaan palaa, koska kaikki on sijoitettu alle public static void main.,
Thanks for reading!