6.3 DRILL — DP-design og rekonstruksjon

Full drill på sjanger H med DP: gjenkjenn et sekvens-/delstrukturproblem, sett opp rekurrensen, fyll tabellen og **rekonstruér** løsningen.

85 min

11 oppgaver

DRILLDP-designrekonstruksjon

Din fremgang i kapitlet

0 / 11 oppgaver

Kapitlets plass i kurset

Bygger på

6.2DP-klassikere — stavkapping, LCS og ryggsekk

Dynamisk programmering er registrert i 16 av de 17 settene i grunnlaget
(94 %). Grunnlaget er de 17 settene fra august 2015 til august 2023 som er
gjennomgått tema for tema — det er nevneren hver gang boka oppgir en prosent.

DP er den ene av fagets to designryggrader. Sammen med maks-flyt dekker de de
aller fleste av de åpne designoppgavene som avslutter hvert ordinære sett — og
det er der toppkarakteren avgjøres.

To sjangre driller vi her:

- Sjanger H — åpen algoritmedesign, altså at du skisserer en algoritme på
fem til ti linjer. Denne sjangeren har fem obligatoriske ledd, og det
vanskeligste er det fjerde: rekonstruksjonen av selve løsningen.
- Sjanger C — håndkjøring, altså at du fyller ut en DP-tabell for hånd og
oppgir det etterspurte — en celle, en rad, eller den ferdige løsningen.

Prioritet: bør sitte.

Den ene feilen som koster mest: å oppgi optimalverdien og stoppe der.
Oppgaven ber om en oppdeling, en delsekvens eller en plan — ikke om
tallet. Dette er felle #6, og den koster typisk et helt ledd av
uttellingen.

Slik er kapitlet lagt opp (85 min):

Innhold	Tid
Løsningsoppskriften, seks steg	ca. 12 min
Gjennomkjørt eksamenscase med margnotater	ca. 16 min
Drill på oppdelingsproblemer	ca. 20 min
Drill på sekvensproblemer	ca. 20 min
Drill på rekonstruksjon og kjøretid	ca. 17 min

— naturlig pausepunkt — etter oppdelingsdrillen. Resten kan tas i en egen
økt.

Forkunnskaper

Dette kapitlet legger ikke til nytt stoff. Det gjør to kapitlers teori til en
ferdighet, og de tre resultatene du trenger i hånden, står her:

1. De to kravene fra kap. 6.1: DP virker når
problemet har optimal substruktur (en optimal helhetsløsning inneholder
optimale delløsninger) og overlappende delproblemer (de samme
delproblemene dukker opp igjen og igjen). Mangler det andre, er
splitt-og-hersk like bra.
2. Kjøretidsregelen fra kap. 6.1:

$\text{kjøretid} = (\text{antall delproblemer}) \times (\text{arbeid per delproblem})$

Den brukes i hver eneste oppgave i dette kapitlet.
3. Rekurrensmønsteret fra kap. 6.2. De tre
klassikerne, ferdig oppfrisket:

Stavkapping — ett kutt om gangen, resten løses rekursivt:

$r[j] = \max_{1 \le i \le j}\big(p_i + r[j-i]\big), \qquad r[0] = 0$

Lengste felles delsekvens (LCS) — sammenlign to tegn, og enten matcher
de eller så hopper du over ett av dem:

$c[i,j] = \begin{cases} 0 & i = 0 \text{ eller } j = 0 \\ c[i-1,j-1] + 1 & x_i = y_j \\ \max(c[i-1,j],\; c[i,j-1]) & \text{ellers} \end{cases}$

Kjøretid $\Theta(nm)$ .

0-1-ryggsekk — ta gjenstanden eller la den ligge:

$c[i,w] = \max\big(c[i-1,w],\; v_i + c[i-1,\,w-w_i]\big)$

Kjøretid $\Theta(nm)$ , der $m$ er kapasiteten som tallverdi — derfor
pseudopolynomisk.

Legg merke til at alle tre har den samme formen: ta et valg i ett steg, og
slå opp den beste løsningen på resten. Det er det mønsteret du leter etter i
en ny innpakning.

Notasjons- og pseudokodeliste

📜Løsningsoppskriften for en DP-designoppgave

Steg 1 — gjenkjenn mønsteret. Se etter en av disse formene:

Innpakningen	Delproblemet
noe skal deles opp i biter (stav, tekst, tidslinje)	«beste verdi for de første $j$ enhetene»
to sekvenser skal sammenlignes (strenger, ruter, hendelser)	«beste verdi for de første $i$ og de første $j$ »
velg eller ikke velg hver gjenstand, med en samlet grense	«beste verdi av de $i$ første, med grense $w$ »
en sti gjennom et rutenett eller en DAG	«beste verdi fram til rute $(i,j)$ »

Steg 2 — definér delproblemet i én setning, med ord. «La

c[i]

være den
høyeste verdien man kan få av de

i

første enhetene.» Uten denne setningen er
rekurrensen uleselig, og den er ett av leddene som gir uttelling.
Steg 3 — skriv rekurrensen, og ta med grunntilfellene. Rekurrensen er
alltid «prøv hvert mulig valg i ett steg, og slå opp den beste løsningen på

resten».
Steg 4 — oppgi fylleorden. Bottom-up krever at delproblemene fylles i en
rekkefølge der alt et delproblem trenger, allerede er beregnet — typisk

stigende $i$ , eller stigende $i$ og $j$ . Alternativt: memoisering, som lar
rekursjonen styre rekkefølgen selv.
Steg 5 — rekonstruér selve løsningen. Lagre valget i hver celle, ikke

bare verdien, og les valgtabellen baklengs fra det ferdige svaret. Si
eksplisitt at rekonstruksjonen koster $O(n)$ eller $O(n+m)$ og ikke øker den
asymptotiske kjøretiden.
Steg 6 — oppgi kjøretiden som antall delproblemer ganger arbeid per

delproblem, med $n$ og $m$ definert i problemets egne størrelser.
Kontrollen før du leverer: har du med alle seks? Det femte er det som
oftest glipper.

✏️Eksempel 1: Gjennomkjørt eksamenscase med margnotater

En stavekontroll skal avgjøre om en sammensatt streng kan deles i ord fra en
ordbok, og i så fall hvilke ord.

Strengen er sykkelstativ, og ordboka inneholder sykkel, stativ, syk,
kel, stat, iv.

Beskriv en DP-løsning: definér delproblemet, skriv rekurrensen, oppgi
kjøretiden, og forklar hvordan du rekonstruerer selve oppdelingen. Kjør den
deretter på strengen.

Steg 1 — mønsteret. Strengen skal deles opp i biter. Det er
oppdelingsmønsteret, og det peker rett på DP.

Margnotat. Å navngi mønsteret er halvparten av jobben, og det er ett av de
fem leddene som gir uttelling. Skriv det i klartekst.

Steg 2 — delproblemet. La ok[j] være sann hvis prefikset tekst[1..j]
kan deles i ord fra ordboka.

Margnotat. Denne setningen skrives med ord, ikke med formler. Uten den er
rekurrensen umulig å lese for den som retter.

Steg 3 — rekurrensen.

$\text{ok}[j] = \bigvee_{0 \le i < j}\Big(\text{ok}[i] \;\wedge\; \text{tekst}[i{+}1..j] \in \text{ordboka}\Big)$

med grunntilfellet $\text{ok}[0] = \text{sann}$ — den tomme strengen er en
gyldig oppdeling.

Margnotat. Grunntilfellet er ikke pynt. Uten $\text{ok}[0] = \text{sann}$
kan aldri det første ordet godkjennes, og hele tabellen blir usann.

Steg 4 — fylleorden. Stigende $j$ fra 1 til $n$ . Da er alle $\text{ok}[i]$
med $i < j$ ferdig beregnet når $\text{ok}[j]$ skal fylles.

Steg 5 — rekonstruksjonen. Lagre i tillegg valg[j] = den $i$ som gjorde
$\text{ok}[j]$ sann. Les så baklengs fra $j = n$ : ordet er
tekst[valg[n]+1..n], og du fortsetter fra $j = \text{valg}[n]$ til du treffer
0.

Margnotat. Dette leddet er hele forskjellen mellom et halvt og et helt svar.
Oppgaven ba om hvilke ord, ikke om ja eller nei.

Steg 6 — kjøretiden. $n+1$ delproblemer, og hvert krever at inntil $n$
delstrenger slås opp i ordboka. Med et oppslag i konstant tid gir det
$\Theta(n^2)$ oppslag, altså $O(n^2)$ når ordlengdene regnes som konstante.
Rekonstruksjonen koster $O(n)$ og øker ikke kjøretiden.

Kjøringen på sykkelstativ (12 tegn):

$j$	Delstreng `tekst[1..j]`	Kan deles?	Siste ordet starter i
0	(tom)	ja	—
1	`s`	nei	—
2	`sy`	nei	—
3	`syk`	ja	$i = 0$ , ordet `syk`
4	`sykk`	nei	—
5	`sykke`	nei	—
6	`sykkel`	ja	$i = 0$ , ordet `sykkel`
7	`sykkels`	nei	—
8	`sykkelst`	nei	—
9	`sykkelsta`	nei	—
10	`sykkelstat`	ja	$i = 6$ , ordet `stat`
11	`sykkelstati`	nei	—
12	`sykkelstativ`	ja	$i = 6$ , ordet `stativ`

Margnotat. Legg merke til

j = 3

: syk finnes i ordboka, så prefikset kan
deles. Men

j = 6

blir sann via sykkel som ett ord, ikke via syk + kel —
begge veier finnes, og algoritmen tar den første den finner. Det spiller ingen
rolle for svaret: begge oppdelingene er gyldige.
Sluttilstanden — det du ville levert på eksamen:
Ja, strengen kan deles: sykkel + stativ.
Margnotat om delvis uttelling. Har du delproblemet, rekurrensen og
kjøretiden, men ikke rekonstruksjonen, ligger du typisk på fire av fem ledd.
Har du bare «ja», har du ett.

Drill: oppdelingsproblemer (~20 min)

Fire oppgaver på det første mønsteret: noe skal deles i biter, og hver bit gir
en verdi.

📝Oppgave 1

Eksamensnivå, sjanger C

En stålstang kan kappes i biter, og en bit av lengde $i$ selges for prisen
$p_i$ :

Lengde $i$	1	2	3	4	5	6	7	8
Pris $p_i$	2	5	9	11	14	19	20	23

a) Fyll ut

r[0..8]

med stavkapping-rekurrensen.
b) Hva er den høyeste inntekten fra en stang av lengde 8?

📝Oppgave 2

Eksamensnivå, sjanger C

Samme prisliste som i oppgave 1.

a) Vis alle leddene i maksimeringen for $r[6]$ .
b) Oppgi den optimale oppdelingen av en stang på lengde 8, og forklar
hvordan du leser den ut av valgtabellen.

📝Oppgave 3

Eksamensnivå, sjanger H

En teksteditor skal bryte en avsnittstekst med $n$ ord i linjer. Å legge ordene
$i$ til $j$ på én linje gir en «styggehetskostnad» $K(i,j)$ som kan slås opp i
konstant tid, eller uendelig hvis ordene ikke får plass. Summen av kostnadene
skal minimeres.

Beskriv en DP-løsning.

📝Oppgave 4

Eksamensnivå, sjanger F

En kandidat foreslår å løse stavkapping grådig: «Kapp alltid av den dyreste
enkeltbiten som får plass, og gjenta med resten.»

Vil det alltid gi optimal inntekt? Svar ja eller nei, og gi et konkret
motbevis.

Drill: sekvensproblemer (~20 min)

Fire oppgaver på det andre mønsteret: to sekvenser skal sammenlignes.

📝Oppgave 5

Eksamensnivå, sjanger C

Finn lengden på den lengste felles delsekvensen av SPRING og STRENG ved å
fylle ut LCS-tabellen.

a) Oppgi den ferdige tabellen $c[0..6, 0..6]$ .
b) Oppgi en lengste felles delsekvens.

📝Oppgave 6

Eksamensnivå, sjanger C…

a) Finn lengden på den lengste felles delsekvensen av ALGORITME og
LOGARITME.
b) Hva er kjøretiden til LCS-algoritmen på to strenger av lengde

n

m

, og hvorfor?

📝Oppgave 7

Eksamensnivå, sjanger H

To turgåere har hver sin logg over hvilke hytter de har overnattet på, i
kronologisk rekkefølge. Turistforeningen vil finne den lengste sekvensen av
hytter begge har besøkt, i samme rekkefølge — men ikke nødvendigvis
etter hverandre.

Beskriv en DP-løsning.

📝Oppgave 8

Eksamensnivå, sjanger F

En kandidat skriver: «LCS-tabellen har $\Theta(nm)$ celler, og rekonstruksjonen
går gjennom hele tabellen. Derfor er rekonstruksjonen også $\Theta(nm)$ , og
kjøretiden dobles.»

Er utsagnet riktig? Svar ja eller nei, og begrunn.

Drill: rekonstruksjon og kjøretid (~17 min)

Tre oppgaver på det leddet som oftest glipper.

📝Oppgave 9

Eksamensnivå, sjanger C

Fire gjenstander skal pakkes i en ryggsekk med kapasitet 9:

Gjenstand	1	2	3	4
Vekt $w_i$	2	3	4	5
Verdi $v_i$	3	4	5	6

a) Fyll ut 0-1-ryggsekk-tabellen

c[0..4, 0..9]

.
b) Oppgi den høyeste verdien, og hvilke gjenstander som velges.

📝Oppgave 10

Eksamensnivå, sjanger E

Oppgi kjøretiden for hver av disse, og si hva $n$ og $m$ er:

a) LCS på to strenger.
b) Stavkapping på en stang av lengde $n$ .
c) 0-1-ryggsekk med $n$ gjenstander og kapasitet $W$ .
d) Rekonstruksjonen i hvert av de tre tilfellene.

📝Oppgave 11

Eksamensnivå, sjanger…

Et vannkraftverk kan hver måned enten kjøre turbinen eller la magasinet fylle
seg. Kjøres turbinen i måned $i$ , gis inntekten $g_i$ , men magasinet må stå
urørt de to neste månedene. Over $n$ måneder skal samlet inntekt
maksimeres.

a) Beskriv en DP-løsning.
b) Oppgi kjøreplanen for $n = 6$ og inntektene $g = 4, 9, 3, 8, 2, 7$ .

Typiske feil

Den første koster mest, og den kommer i nesten hver designoppgave.

- Å oppgi bare optimalverdien. Dette er felle #6. Oppgaven ber om en
oppdeling, en delsekvens eller en plan — og da må du lagre valgene og lese
dem baklengs. Si samtidig at rekonstruksjonen ikke øker den asymptotiske
kjøretiden.
- Å påstå at rekonstruksjon er «gratis». Også felle #6, den andre veien.
Den krever at valgene faktisk lagres. Riktig formulering er «krever lagrede
valg, men øker ikke kjøretiden».
- Å bruke DP på et problem uten overlappende delproblemer. Da er
splitt-og-hersk like bra, og DP-tabellen er bare overhead. Se
kap. 6.1.
- Å definere delproblemet upresist. «La $c[i]$ være den beste verdien» er
ikke nok — best for hva? Setningen skal si nøyaktig hvilken delmengde eller
hvilket prefiks $i$ står for.
- Å glemme grunntilfellene. Uten $r[0] = 0$ eller $\text{ok}[0] = \text{sann}$ kollapser hele tabellen.
- Å oppgi feil fylleorden. Bottom-up krever at alt et delproblem trenger,
er beregnet på forhånd. For LCS betyr det stigende $i$ og stigende $j$ .
- Å regne $\Theta(nW)$ som polynomisk i ryggsekk. $W$ er en tallverdi,
og algoritmen er derfor pseudopolynomisk. Se
kap. 6.2.
- Å bruke en grådig regel der DP kreves. Stavkapping mangler den grådige
valg-egenskapen: det lokalt beste kuttet kan ødelegge for resten.

Og den gjennomgående: å skrive mer enn de fem leddene. Et designsvar er
fem til ti linjer, og lengre svar gir ingen ekstra uttelling.

Kjøretidene du kan bli spurt om i en deloppgave

Problem	Delproblemer	Arbeid per	Kjøretid	Rekonstruksjon
Stavkapping	$n$	$O(n)$	$\Theta(n^2)$	$O(n)$
LCS	$\Theta(nm)$	$\Theta(1)$	$\Theta(nm)$	$O(n+m)$
0-1-ryggsekk	$\Theta(nW)$	$\Theta(1)$	$\Theta(nW)$ — pseudopolynomisk	$O(n)$
Ordsplitting	$n$	$O(n)$	$O(n^2)$	$O(n)$
Linjebryting	$n$	$O(n)$	$\Theta(n^2)$	$O(n)$
Utvelgelse langs en tidslinje	$n$	$\Theta(1)$	$\Theta(n)$	$O(n)$

Én presisering som er verdt å ta med seg. Rekonstruksjonen er alltid et
lavere ledd enn tabellutfyllingen — den følger én sti gjennom tabellen, ikke
alle cellene. Den setningen hører hjemme i hvert eneste designsvar, og den er
kort nok til å koste ingenting.

Begrepsbank

Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp
har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet
gjelder kjernestoffet.

De fem leddene i et DP-designsvar

navngi problemet og paradigmet, definér delproblemet, skriv rekurrensen med grunntilfeller, rekonstruér løsningen, og oppgi kjøretiden. Det fjerde leddet er det som oftest glipper. Mangler ett ledd, er svaret ufullstendig — også når resten er riktig.

Å definere delproblemet

c[i]

Valgtabell

\Theta(1)

Rekonstruksjon

O(n)

Felle #6 — rekonstruksjonens pris

å påstå enten at rekonstruksjon er gratis, eller at den dobler kjøretiden. Riktig: den krever lagrede valg, men er et lavere ledd og øker ikke den asymptotiske kjøretiden. Den vanligste varianten er å oppgi optimalverdien og stoppe der.

Fylleorden

i

Kjøretidsregelen for DP

\text{kjøretid} = (\text{antall delproblemer}) \times (\text{arbeid per delproblem})

Oppdelingsmønsteret

j

Sekvensmønsteret

i

Sjanger H — åpen algoritmedesign

oppgavetypen der du skisserer en algoritme på fem til ti linjer. Fem obligatoriske ledd, og rekonstruksjonen er det tyngste. De siste tre til fem oppgavene i hvert ordinære sett er av denne typen — det er der toppkarakteren avgjøres.

Repetisjonsoppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.