0/1 Knapsack ja tilan optimointi
Johtakaa 0/1 knapsack -rekursio, täyttäkää 2D-taulukko ja supistakaa se sitten 1D-taulukoksi käymällä kapasiteetit läpi käänteisessä järjestyksessä.
0/1 Knapsack ja tilan optimointi on ilmainen Valmistautuminen ohjelmointihaastatteluihin-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 Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
0/1-reppuongelma
0/1-reppuongelmassa annettuna on n esinettä, joista kullakin on paino w[i] ja arvo v[i], sekä kapasiteetiltaan W oleva reppu. Valitkaa esineet siten, että kokonaisarvo maksimoituu eikä kapasiteetti ylity. Kukin esine valitaan täsmälleen kerran (0 = ohita, 1 = valitse). Tämä on malliesimerkki suuresta joukosta haastattelujen DP-ongelmia, kuten ongelmista partition-equal-subset-sum ja target-sum.
DP-tila ja rekurrenssi
Määritellään dp[i][c] ensimmäisten i esineen suurimmaksi mahdolliseksi arvoksi kapasiteetilla c. Esineelle i on kaksi vaihtoehtoa: ohitetaan se (dp[i-1][c]) tai valitaan se, jos w[i] <= c (dp[i-1][c-w[i]] + v[i]). Rekurrenssi on: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]), kun w[i] <= c, ja muussa tapauksessa dp[i][c] = dp[i-1][c]. Alkutilanne: dp[0][c] = 0 kaikilla c:n arvoilla.
2D-DP-taulukon toteutus
2D-taulukossa on (n+1) x (W+1) alkiota, ja se täytetään rivi riviltä jokaiselle esineelle. Kun kaikki rivit on täytetty, dp[n][W] sisältää suurimman mahdollisen arvon. Aikavaativuus on O(n × W) ja tilavaativuus O(n × W) — kyseessä on pseudopolynominen vaativuus, joka on tehokas, kun W on pieni.
def knapsack_2d(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for c in range(W+1):
dp[i][c] = dp[i-1][c] # skip item i
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
return dp[n][W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_2d(weights, values, 8)) # 10Miksi kapasiteetti käydään läpi käänteisessä järjestyksessä 1D-DP:ssä
Keskeinen havainto on, että rivi i riippuu vain rivistä i-1. Siksi voimme käyttää yhtä 1D-taulukkoa ja päivittää sitä paikallaan. Jos kuitenkin käymme kapasiteetit c läpi vasemmalta oikealle (pienestä suureen), esine i voidaan laskea kahdesti — voisimme käyttää päivitettyä arvoa c-w[i]:lle, joka sisältää jo esineen i. Käyminen läpi oikealta vasemmalle (suuresta pienempään) varmistaa, että kutakin esinettä käytetään enintään kerran yhden rivipäivityksen aikana.
# Forward iteration (WRONG for 0/1 knapsack - counts items multiple times)
# for c in range(W+1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] may already use item i
# Backward iteration (CORRECT for 0/1 knapsack)
# for c in range(W, w-1, -1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] still from previous rowTilaa optimoiva 1D-toteutus
Säilyttämällä vain yhden taulukon ja käymällä kapasiteetit läpi arvosta W arvoon w[i] asti saavutamme saman tuloksen kuin 2D-taulukolla, mutta tilavaativuus on O(W). Aikavaativuus säilyy muodossa O(n × W). Tämä tilan optimointi on tärkeä muistaa — haastattelijat pyytävät usein pienentämään 2D-reppuongelman 1D-muotoon.
def knapsack_1d(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for c in range(W, w - 1, -1): # iterate RIGHT TO LEFT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_1d(weights, values, 8)) # 10Valittujen esineiden palauttaminen
Jos haluatte selvittää, mitkä esineet valittiin, tarvitsette koko 2D-taulukon. Kun taulukko on täytetty, aloittakaa kohdasta dp[n][W] ja jäljittäkää ratkaisu taaksepäin: jos dp[i][c] != dp[i-1][c], esine i valittiin — vähentäkää sen paino arvosta c ja siirtykää riville i-1. Jatkakaa, kunnes i = 0. 1D-optimointi poistaa tämän palautusmahdollisuuden.
def knapsack_with_items(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for c in range(W+1):
dp[i][c] = dp[i-1][c]
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
# Reconstruct
selected, c = [], W
for i in range(n, 0, -1):
if dp[i][c] != dp[i-1][c]:
selected.append(i-1)
c -= weights[i-1]
return dp[n][W], selected[::-1]
print(knapsack_with_items([2,3,4,5],[3,4,5,6],8))Käytännön esimerkki: kokonaisarvon maksimointi
Tarkastellaan esineitä: weights=[2,3,4,5], values=[3,4,5,6], W=8. Optimaalinen ratkaisu on valita painoltaan 3 oleva esine (arvo 4) ja painoltaan 5 oleva esine (arvo 6) — kokonaispaino on 8 ja arvo 10. Painoltaan 2 ja 5 olevien esineiden valitseminen tuottaa kokonaisarvoksi 9. Painoltaan 2 ja 3 olevien esineiden valitseminen tuottaa arvoksi 7. DP löytää oikein maksimiarvon 10. Huomatkaa, että ahne menetelmä (suurimman arvo/paino-suhteen valitseminen) valitsisi ensin esineen, jonka suhde on 1.5 (paino 2, arvo 3) — tämä ei aina ole optimaalista.
Murtoreppuongelma verrattuna 0/1-reppuongelmaan
Murtoreppuongelmassa esineistä voidaan ottaa murto-osia. Sen voi ratkaista ahneesti järjestämällä esineet arvo/paino-suhteen mukaan. 0/1-reppuongelmassa esineet ovat jakamattomia — ahne menetelmä epäonnistuu, joten tarvitaan DP:tä. Haastattelijat käyttävät tätä eroa testatakseen, tiedättekö, milloin ahnetta menetelmää voi käyttää. Jos kysymys koskee murtoreppuongelmaa, mainitkaa heti ahne menetelmä ja järjestäminen; jos kyseessä on 0/1-reppuongelma, käyttäkää DP:tä.
# Fractional knapsack: greedy by value/weight ratio
def fractional_knapsack(weights, values, W):
items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
total = 0
for v, w in items:
if W >= w:
total += v; W -= w
else:
total += v * (W / w); break
return total
print(fractional_knapsack([2,3,4,5],[3,4,5,6],8))Pseudopolynominen aikavaativuus
0/1-reppuongelma on NP-täydellinen, mutta voimme ratkaista sen ajassa O(nW). Ristiriita selittyy sillä, että O(nW) on pseudopolynominen: W on arvo eikä syötteen koko. W:n binääriesitys vaatii O(log W) bittiä, joten todellinen vaativuus on O(n × 2^(log W)), joka on eksponentiaalinen suhteessa syötteen kokoon. Kun W on pieni (esimerkiksi 10⁴), DP on käytännöllinen; kun W voi olla 10⁹, tarvitaan muita lähestymistapoja.
Haastattelijan jatkokysymys: suuri kapasiteetti
Jos haastattelija asettaa W:lle erittäin suuren rajoituksen (esimerkiksi 10⁹), mutta n on pieni, tavallinen DP ei toimi. Vaihtoehtoja ovat: (1) meet-in-the-middle ajassa O(2^(n/2) × n), (2) ahne approksimaatio murtoreppuongelman tapauksessa tai (3) haarautuminen ja rajaaminen. Useimmissa haastatteluongelmissa, joissa W <= 10⁵, odotettu vastaus on 1D-DP käänteisessä järjestyksessä.
Meet-in-the-middle suurelle kapasiteetille
Kun W on erittäin suuri mutta n pieni (esimerkiksi n=40), tavallinen O(nW)-DP ei ole mahdollinen, mutta kaikkien vaihtoehtojen läpikäynti 2^n:n ajassa on liian hidasta. Meet-in-the-middle jakaa esineet kahteen puolikkaaseen, luettelee kummankin puolikkaan kaikki 2^(n/2) osajoukkoa ja yhdistää ne optimaalisesti. Järjestäkää toinen puolikas painon mukaan ja käyttäkää sitten kunkin toisen puolikkaan osajoukon kohdalla binäärihakua löytääksenne kapasiteetin rajoissa parhaan parin. Aikavaativuus on O(2^(n/2) × n), joten menetelmä on käytännöllinen arvoon n=40 asti.
Pikatesti
Testatkaa tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheen ymmärtämistänne.
Oppitunnin yhteenveto
Tässä oppitunnissa opitte: 0/1-reppuongelman DP-tila dp[i][c] kuvaa suurinta arvoa, joka voidaan saavuttaa i esineellä ja kapasiteetilla c, rekurrenssi valitsee kunkin esineen kohdalla, ohitetaanko se vai otetaanko se mukaan, ja 1D-tilan optimointi käy kapasiteetit läpi oikealta vasemmalle estääkseen esineiden laskemisen kahdesti. Seuraavaksi tutustumme rajoittamattomaan reppuongelmaan, jossa esineitä voidaan käyttää uudelleen, ja sovellamme sitä Coin Change II -ongelmaan.
Opi Valmistautuminen ohjelmointihaastatteluihin 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
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”0/1 Knapsack ja tilan optimointi” ilmainen?
Kyllä – oppitunnin ”0/1 Knapsack ja tilan optimointi” 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 Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”0/1 Knapsack ja tilan optimointi”?
Johtakaa 0/1 knapsack -rekursio, täyttäkää 2D-taulukko ja supistakaa se sitten 1D-taulukoksi käymällä kapasiteetit läpi käänteisessä järjestyksessä. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-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 Knapsack ja tilan optimointi”-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ä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-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 Knapsack ja tilan optimointi
- Rajoittamaton Knapsack ja Coin Change II
- Osajoukkojen yhtä suuri summa
- Tavoitesumma positiivisilla ja negatiivisilla merkeillä