Tilankäytöltään optimoitu reppu
Pienennä kaksiulotteinen taulukko yhdeksi riviksi
Tilankäytöltään optimoitu reppu on ilmainen Competitive Programming Academy-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Competitive Programming Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Miksi tila kannattaa optimoida
Kokonainen taulukko kuluttaa n kertaa cap muistia, mikä voi kasvaa valtavaksi suurilla syötteillä. Tilankäytön optimointi supistaa sen yhteen uudelleenkäytettävään riviin.
Vain viimeinen rivi merkitsee
Huomaatte, että jokainen solu lukee vain edellistä riviä, ei mitään sitä vanhempaa. Siksi koko ruudukkoa ei tarvitse koskaan tallentaa kerralla.
Supistakaa yhteen taulukkoon
Säilyttäkää yksi dp-taulukko, jonka pituus on cap+1. Kun käsittelette esineitä, korvaatte taulukon sisällön paikallaan uuden rivin esittämiseksi.
dp = [0] * (cap + 1)Uudelleenkäytön ansa
Jos käytte kapasiteetit läpi vasemmalta oikealle, dp[w - wt[i]] on ehkä jo päivitetty saman esineen kohdalla. Tällöin voisitte ottaa esineen i kahdesti.
Käykää kapasiteetit taaksepäin
Ratkaisu on käydä kapasiteetit läpi suuresta pienempään. Taaksepäin eteneminen takaa, että dp[w - wt[i]] sisältää edelleen edellisen kierroksen arvon.
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Miksi taaksepäin eteneminen toimii
Kun laskette arvon dp[w], pienempi indeksi w - wt[i] on tällä kierroksella yhä koskematon, joten se vastaa suunnitellusti ylempää riviä.
Pysähtykää esineen painoon
Kapasiteetit, jotka ovat pienempiä kuin wt[i], eivät voi sisältää esinettä, joten silmukka päättyy kohtaan wt[i]. Niiden ohittaminen säästää muutaman tarpeettoman kierroksen.
Koko silmukka
Koko ratkaisu koostuu kahdesta sisäkkäisestä silmukasta yhden taulukon ympärillä. Esineet ulommassa silmukassa, kapasiteetti taaksepäin sisemmässä, ja vastaus saadaan lopuksi.
for i in range(n):
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Lukekaa viimeinen solu
Kaikkien esineiden käsittelyn jälkeen dp[cap] sisältää suurimman arvon. Se on sama luku, jonka kaksiulotteinen taulukko tuottaisi, mutta paljon pienemmällä muistinkulutuksella.
Sama aika, vähemmän muistia
Algoritmi ei nopeutunut, vaan sen aikavaativuus on edelleen n kertaa cap. Vähensitte ainoastaan muistin neliöllisestä lineaariseksi.
Milloin tästä on hyötyä
Tämä keino auttaa, kun cap on suuri ja kaksiulotteinen ruudukko ylittäisi muistirajan. Se on kilpailuohjelmoinnin perustekniikka, joka kannattaa opetella ulkoa.
Pikatarkistus
Testatkaa yksiulotteisen reppuongelman tärkeintä sääntöä.
Kertaus
Supistitte kaksiulotteisen taulukon yhdeksi taulukoksi ja kävitte kapasiteetit taaksepäin läpi säilyttääksenne oikeellisuuden. Näin vaihdoitte neliöllisen muistinkulutuksen lineaariseen. 🚀
Opi Python tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”Tilankäytöltään optimoitu reppu” ilmainen?
Kyllä – oppitunnin ”Tilankäytöltään optimoitu reppu” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Competitive Programming Academy-kurssin, päivitä CoddyKit PROhon. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Tilankäytöltään optimoitu reppu”?
Pienennä kaksiulotteinen taulukko yhdeksi riviksi Harjoittelet Competitive Programming Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Competitive Programming Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Competitive Programming Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.
Kuinka kauan ”Tilankäytöltään optimoitu reppu”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Competitive Programming Academy-oppitunnilla?
Kyllä. Jokainen Competitive Programming Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- 0/1-reppu: ota tai jätä
- Tilankäytöltään optimoitu reppu
- Rajoittamaton reppu ja vaihtoraha-DP
- Osajoukkosumma ja ositus