- Bliver fyldt
- Læses
- Svar
Rygsækproblemet
Du kan kun bære en vis vægt, og hver genstand har en vægt og en værdi. Hvilke genstande tager du med for at bære mest værdi? Hvis du prøver alle kombinationer, fordobles arbejdet for hver genstand. En tabel med en række pr. genstand og en kolonne pr. kapacitet finder den bedste rygsæk én celle ad gangen. Tryk på en genstand for at lægge den i rygsækken, og tryk på den igen (i rygsækken eller på hylden) for at tage den ud. Rygsækken fyldes efter vægt, og felterne viser de dollars, du har pakket, sammenlignet med det bedst mulige. Tryk på Bedste pakning for at se den bedste rygsæk. I panelet kan du ændre genstandenes kilo og dollars, tilføje eller fjerne genstande og indstille rygsækkens kapacitet. Visningen Tabel viser, hvordan dynamisk programmering finder den bedste rygsæk: tryk på Afspil for at se tabellen blive fyldt, eller på Trin og Tilbage for at gå ét trin ad gangen, og træk i trinskyderen for at springe hvorhen du vil. Hver række tilføjer én genstand, hver kolonne er en kapacitet i kilo, og hver celle indeholder flest mulige dollars, der kan være. Når tabellen er valgt, går piletasterne et trin frem eller tilbage, mellemrumstasten afspiller og sætter på pause, og Home og End springer til starten og slutningen.
Sådan virker det
- Tryk på kasserne for at pakke dem i rygsækken, og se den fyldes op efter vægt i kilo.
- Prøv at nå den bedst mulige værdi i dollars, eller tryk på Bedste pakning for at se den bedste rygsæk.
- Åbn visningen Tabel, og tryk på Afspil for at se hver celle vælge mellem at pakke og udelade en genstand.
Sådan virker tabellen
Hver række tilføjer én genstand, og hver kolonne er en kapacitet fra 0 op til rygsækkens. En celle indeholder den største værdi, der kan være i den kapacitet med genstandene til og med dens række. Uden den nye genstand er det cellen ovenover. Med den, hvis den kan være der, er det genstandens værdi plus den bedste værdi for den vægt, der er tilbage, som står i rækken ovenover, genstandens vægt til venstre. Cellen beholder den største af de to. Den første række, uden genstande, er lutter nuller.
Læs genstandene tilbage
Cellen nederst til højre er den bedste værdi. For at finde genstandene starter du der og sammenligner med cellen ovenover: Er den den samme, var den sidste genstand ikke nødvendig; er den større, er genstanden i rygsækken, så træk dens vægt fra, og gå til den kolonne. Gå én række op hver gang, indtil du når den første række. Appen viser tilbagelæsningen i orange og viser de pakkede genstande under tabellen.
Ofte stillede spørgsmål
Hvad betyder 0/1 i 0/1-rygsækproblemet?
Hver genstand pakkes én gang eller slet ikke, aldrig delvist og aldrig to gange. Hvis genstande kunne deles, som riskorn, ville det være optimalt at pakke den bedste værdi pr. vægt først; det er det fraktionelle rygsækproblem.
Hvorfor ikke pakke den bedste værdi pr. vægt først?
Fordi hele genstande kan efterlade huller. Med en kapacitet på 7 og genstande med vægt 1, 3, 4 og 5 og værdi 1, 4, 5 og 7 har genstanden med vægt 5 den bedste værdi pr. vægt, og så er der kun plads til genstanden med vægt 1, i alt 8. Genstandene med vægt 3 og 4 er tilsammen 9 værd.
Hvor hurtig er rygsækalgoritmen?
Tabellen har (antal genstande + 1) gange (kapacitet + 1) celler, og hver fyldes i ét trin. Det går hurtigt for små kapaciteter, men en kapacitet kan være et enormt tal, så generelt er problemet NP-svært; tabelmetoden kaldes pseudopolynomiel.
Kan den samme genstand pakkes to gange?
Ikke her. I det ubegrænsede rygsækproblem kan hver genstand tages et vilkårligt antal gange; tabellen læser så cellen til venstre i samme række i stedet for rækken ovenover, som i appen om byttepenge.
Bliver noget sendt nogen steder hen?
Nej. Alt beregnes i din browser, og dine seneste indstillinger bliver i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor