Competitive Programming Academy · Oppitunti

0/1-reppu: ota tai jätä

Maksimoi arvo painorajoituksen puitteissa

Oppitunti 1/413 vaihetta

0/1-reppu: ota tai jätä on ilmainen Competitive Programming Academy-oppitunti CoddyKitissä. Tämä on oppitunti 1/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.

Reppuongelman tarina

Teillä on painorajoitettu reppu ja kasa esineitä. 0/1-reppuongelmassa kysytään, mitkä esineet maksimoivat arvon ylittämättä repun kapasiteettia? 🎒

Ottakaa tai jättäkää

Merkintä 0/1 tarkoittaa, että jokainen esine joko otetaan kokonaan tai jätetään kokonaan ottamatta. Puolikasta esinettä ei voi ottaa, joten jokainen valinta on kyllä tai ei.

Miksi ahne menetelmä epäonnistuu

Halvimman tai arvokkaimman esineen ottaminen ensin voi tuhlata kapasiteettia. Ahne oikotie ei toimi tässä, joten todelliset yhdistelmät on tutkittava.

Kaksi syötettä

Teille annetaan kaksi rinnakkaista listaa: kunkin esineen paino ja arvo sekä yksi kapasiteetti. Esineen i paino on wt[i] ja arvo val[i].

wt  = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7

Määritelkää tila

Olkoon dp[i][w] suurin arvo, jonka ensimmäisistä i esineestä voi saada kapasiteetilla w. Tilan täsmällinen nimeäminen on koko tehtävän ydin.

Ohittamisvalinta

Jos jätätte esineen i ottamatta, arvoksi jää se, mikä teillä jo oli: dp[i-1][w]. Muu kapasiteetti säilyy koskemattomana.

Ottamisvalinta

Jos otatte esineen i, lisäätte sen arvon ja pienennätte kapasiteettia: val[i] + dp[i-1][w - wt[i]]. Tämä on sallittua vain, kun w on vähintään wt[i].

Valitkaa parempi haara

Rekurenssi säilyttää yksinkertaisesti kahdesta vaihtoehdosta suuremman arvon max-funktion avulla. Jokainen solu luottaa sen alapuolella jo laskettuihin vastauksiin.

dp[i][w] = max(dp[i-1][w],
               val[i] + dp[i-1][w - wt[i]])

Perusrivi

Kun esineitä on nolla, mukana voi olla nolla-arvoinen määrä tavaraa millä tahansa kapasiteetilla. Tämä perustapaus täyttää ensimmäisen rivin nollilla, joiden päälle rakennetaan.

dp = [[0] * (cap + 1) for _ in range(n + 1)]

Täyttäkää taulukko

Käsitelkää esineet ulommassa silmukassa ja kapasiteetit sisemmässä. Jokainen solu lukee vain yläpuolista riviä, joten yksi läpikäynti täyttää kaiken.

for i in range(1, n + 1):
    for w in range(cap + 1):
        dp[i][w] = dp[i-1][w]

Lukekaa vastaus

Oikean alakulman solu dp[n][cap] sisältää kaikkien esineiden ja koko kapasiteetin suurimman arvon. Tämä yksi solu on lopullinen vastauksenne.

Pikatarkistus

Testatkaa 0/1-reppuongelman ydinrekurenssi.

Vastaa interaktiivisessa oppitunnissa

Kertaus

Opitte 0/1-reppuongelman: jokainen esine joko otetaan tai jätetään, dp[i][w] säilyttää paremman vaihtoehdoista ohittamisen ja ottamisen välillä, ja dp[n][cap] on vastaus. 🎉

Aloita maksutta

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

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”0/1-reppu: ota tai jätä” ilmainen?

Kyllä – oppitunnin ”0/1-reppu: ota tai jätä” 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 ”0/1-reppu: ota tai jätä”?

Maksimoi arvo painorajoituksen puitteissa 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 1/4.

Kuinka kauan ”0/1-reppu: ota tai jätä”-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

← Takaisin: Competitive Programming Academy