Fraksjonell ryggsekk etter forholdstall
Ta først det høyeste forholdet mellom verdi og vekt
Fraksjonell ryggsekk etter forholdstall er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Oppsettet for ryggsekkproblemet
Du har gjenstander med en verdi og en vekt, samt en sekk med begrenset kapasitet. Målet er å ta med deg så høy totalverdi som mulig. 🎒
Brøkvarianten kan deles opp
I den fraksjonelle varianten kan du ta en del av en gjenstand, for eksempel en halv sekk korn. Det er denne friheten som gjør at en grådig algoritme fungerer her.
Verdi per vekt
Det viktigste målet er hver gjenstands forhold mellom verdi og vekt. Et høyt forhold betyr at mye verdi får plass på svært liten plass.
ratio = value / weightSorter etter beste forhold
Sorter gjenstandene etter verdi per vekt, med høyest først. Den grådige planen er å fortsette å ta den tilgjengelige gjenstanden med høyest verdietetthet.
items.sort(key=lambda i: i[0] / i[1], reverse=True)Ta hele så lenge det passer
Gå gjennom den sorterte listen, og ta hver gjenstand helt hvis den fortsatt får plass i den gjenværende kapasiteten. Legg hele verdien til totalen.
if weight <= cap:
total += value
cap -= weightFyll det siste tomrommet
Når en gjenstand er for stor, tar du en brøkdel som fyller den gjenværende plassen nøyaktig. Da er sekken full, og du stopper.
total += value * (cap / weight)Hvorfor rekkefølgen etter forhold fungerer
Hver kapasitetsenhet bør inneholde mest mulig verdi, så den tetteste gjenstanden må tas først. Hvis du bytter inn en med lavere tetthet, mister du bare verdi.
0/1-sekkproblemet er annerledes
Hvis gjenstander ikke kan deles, fungerer en grådig strategi basert på forholdstallet dårlig. 0/1-versjonen trenger dynamisk programmering, ikke denne enkle sorteringen.
Kjøretiden
Sortering etter forholdstall koster O(n log n), og løkken som fyller sekken, er lineær. Det er mer enn raskt nok for typiske grenser i konkurranseoppgaver.
Pass på den siste brøken
Bruk flyttall eller eksakte rasjonale tall for den delvise gjenstanden. Hvis De avkorter for tidlig, kan De miste verdi og få feil svar.
Hvor det brukes
Tenk på lasting av last, blanding av drivstoff eller oppdeling av ressurser. Når deler kan deles opp, er en grådig strategi basert på forholdstallet verktøyet De trenger.
Rask kontroll
De fyller en sekk i det fraksjonelle sekkproblemet.
Oppsummering
Sorter gjenstandene etter verdi per vekt, ta hele gjenstander så lenge de får plass, og fyll deretter resten av sekken med en brøkdel. Denne grådige strategien er bare optimal når gjenstandene kan deles. 🚀
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Fraksjonell ryggsekk etter forholdstall» gratis?
Ja – hele teksten i «Fraksjonell ryggsekk etter forholdstall» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Fraksjonell ryggsekk etter forholdstall»?
Ta først det høyeste forholdet mellom verdi og vekt Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.
Hvor lang tid tar leksjonen «Fraksjonell ryggsekk etter forholdstall»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Den grådige tankemåten
- Aktivitetsutvalg etter tidligste slutt
- Fraksjonell ryggsekk etter forholdstall
- Oppdag når grådige løsninger feiler