Competitive Programming Academy · Oppitunti

Rajoittamaton reppu ja vaihtoraha-DP

Käytä alkioita kuinka monta kertaa tahansa

Oppitunti 3/413 vaihetta

Rajoittamaton reppu ja vaihtoraha-DP on ilmainen Competitive Programming Academy-oppitunti CoddyKitissä. Tämä on oppitunti 3/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.

Rajoittamaton määrä esineitä

Rajoittamattomassa reppuongelmassa jokaisen esineen voi ottaa niin monta kertaa kuin haluaa. Ajatelkaa automaatin kolikoita, ei kiinteää esinekasausta.

Yksi pieni muutos

0/1-versioon verrattuna vain silmukan suunta vaihtuu. Rajoittamattomien esineiden tapauksessa käykää kapasiteetit eteenpäin, pienestä suureen.

Eteenpäin tapahtuva uudelleenkäyttö on tarkoitus

Eteenpäin edetessä dp[w - coin] voi jo sisältää saman esineen. Tämä tarkoituksellinen uudelleenkäyttö mahdollistaa esineen ottamisen uudelleen.

Tutustukaa kolikkorahanvaihtoon

Klassisessa kolikkorahanvaihto-ongelmassa etsitään pienintä kolikkojen määrää, jolla summa saadaan muodostettua. Kyseessä on rajoittamaton DP, jossa maksimin sijaan käytetään minimiä.

Määritelkää tila

Olkoon dp[a] niiden kolikoiden pienin määrä, joilla summa a voidaan muodostaa. Alustakaa dp[0] = 0, koska nollan muodostamiseen ei tarvita kolikoita.

dp = [float("inf")] * (amount + 1)
dp[0] = 0

Käyttäkää ääretöntä mahdottomille tapauksille

Saavuttamattomat summat alustetaan arvolla ääretön. Jos summa on lopussa edelleen ääretön, mikään kolikkoyhdistelmä ei voi muodostaa sitä.

Siirtymä

Kokeilkaa jokaisella kolikolla parantaa jokaista summaa, johon se voi yltää. Käyttäkää yhtä kolikkoa enemmän kuin jäljelle jäävän pienemmän summan paras tulos.

for coin in coins:
    for a in range(coin, amount + 1):
        dp[a] = min(dp[a], dp[a - coin] + 1)

Miksi etenemisjärjestys on eteenpäin

Kun käytte summat kasvavassa järjestyksessä, dp[a - coin] voi jo sisältää tämän kolikon. Näin yksi kolikko voi vaikuttaa useita kertoja.

Laskekaa sen sijaan tapoja

Korvatkaa min+1 summalla laskeaksenne, kuinka monta tapaa kunkin summan muodostamiseen on. Kolikkosilmukka ulompana estää järjestysten laskemisen kahdesti.

for coin in coins:
    for a in range(coin, amount + 1):
        dp[a] += dp[a - coin]

Lukekaa tulos

Vastaus löytyy kohdasta dp[amount]. Minimiversiossa ääretön arvo tarkoittaa, ettei kohdesummaa voi muodostaa.

0/1 ja rajoittamaton versio

Muistakaa yksi vaihtokytkin: kapasiteetin käsittely taaksepäin tarkoittaa, että kutakin esinettä käytetään kerran, kun taas eteenpäin käsittely sallii rajattoman käytön. Sama taulukko, vastakkainen etenemisjärjestys.

Pikatarkistus

Testatkaa, mikä tekee reppuongelmasta rajoittamattoman.

Vastaa interaktiivisessa oppitunnissa

Kertaus

Vaihdoitte silmukan etenemään eteenpäin mahdollistaaksenne rajattoman uudelleenkäytön ja rakensitte kolikkorahanvaihdon käyttämällä minimiä pienimmän kolikkojen määrän etsimiseen tai summaa kaikkien tapojen laskemiseen. 💰

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 ”Rajoittamaton reppu ja vaihtoraha-DP” ilmainen?

Kyllä – oppitunnin ”Rajoittamaton reppu ja vaihtoraha-DP” 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 ”Rajoittamaton reppu ja vaihtoraha-DP”?

Käytä alkioita kuinka monta kertaa tahansa 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 3/4.

Kuinka kauan ”Rajoittamaton reppu ja vaihtoraha-DP”-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