6.2 DP-klassikere — stavkapping, LCS og ryggsekk

Rod-Cutting (stavkapping), LCS (lengste felles delsekvens) og 0-1-Knapsack (ryggsekk) — de navngitte DP-problemene og deres rekurrenser.

55 min

8 oppgaver

DP-klassikerestavkappingLCSryggsekk

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Bygger på

6.1Dynamisk programmering — mekanikk

Brukes videre i

6.3DRILL — DP-design og rekonstruksjon

De navngitte DP-problemene hører til et tema som er registrert i 94 % (16 av de 17 settene i grunnlaget) — de 17 settene fra august 2015 til august 2023 som er gjennomgått tema for tema. Nevneren er den samme hver gang boka oppgir en prosent.

To sjangre henter herfra, og de skrives ut i klarspråk:

- Sjanger C — håndkjøring: du utfører algoritmen steg for steg og leverer bare sluttilstanden i det formatet oppgaven ber om. For dette kapitlet betyr det som regel en utfylt tabell, en lengde eller en oppdeling.
- Sjanger H — åpen algoritmedesign: du får et problem i ny innpakning og skisserer en algoritme på fem–ti linjer. De tre problemene her er malene du gjenkjenner innpakningene mot.

Ett faktum går igjen som et rent kunnskapsspørsmål, og det er verdt å merke seg allerede nå: 0-1-ryggsekk løses i $\Theta(nm)$ , og det er ikke det samme som polynomisk tid. Uttrykket kalles pseudopolynomisk, og begrepet innføres i dette kapitlet — det er koblingen videre til teorien om vanskelige problemer i Del 7.

Prioritet: bør sitte. Rekurrensene her er korte nok til å pugges, men det er ikke poenget: du skal kunne utlede dem ved å se på det siste valget, for det er den ferdigheten en designoppgave faktisk måler.

Forkunnskaper

Dette kapitlet forutsetter mekanikken fra kap. 6.1: optimal substruktur, overlappende delproblemer, skillet mellom memoisering og utfylling nedenfra og opp, og at rekonstruksjon krever en lagret valgtabell. Alle tre problemene her er den mekanikken anvendt på et navngitt problem.

I tillegg trenger du:

- kap. 1.1 — $\Theta$ mot $O$ , og hvorfor det er et bevisst valg hvilken du skriver.
- kap. 1.5 — å summere en rekke. Stavkapping gir summen $1 + 2 + \dots + n = n(n+1)/2$ , og den skal du kjenne igjen.

Ordet pseudopolynomisk dukker også opp om Ford-Fulkerson i kap. 5.2, men du trenger ikke ha lest det kapitlet: begrepet bygges opp fra grunnen av her, i den formen ryggsekkproblemet krever.

Notasjons- og pseudokodeliste

Stavkapping — når oppdelingen er verdt mer enn hele (~15 min)

Et metallverksted kjøper aluminiumsprofiler i åtte meters lengder og selger dem videre i standardlengder. Prisen per lengde er ikke proporsjonal med lengden: korte biter er dyre per meter fordi kundene kjøper dem enkeltvis, og de lengste er billige per meter fordi de er tunge å håndtere. Spørsmålet verkstedet stiller hver morgen er: hvordan skal denne profilen kappes for å gi mest mulig?

Dette er stavkapping (rod cutting), og det er det enkleste av de navngitte DP-problemene. Grepet er det samme som i kap. 6.1: se på ett valg, og la resten være et mindre delproblem av samme type.

Det naturlige valget her er lengden på det første stykket. Kapper du først av $i$ meter, får du $p_i$ for det stykket, og resten er en stav av lengde $j - i$ som du løser på nøyaktig samme måte. Prøver du alle lovlige $i$ , har du rekurrensen:

$r_j = \max_{1 \le i \le j}\big(p_i + r_{j-i}\big), \qquad r_0 = 0$

Intuisjon: det finnes ingen grunn til å behandle det første stykket spesielt — vi kunne like gjerne sett på det siste. Poenget er at ett valg deler problemet i «et stykke vi tar betalt for nå» og «et mindre stavkappingsproblem». Grunntilfellet $r_0 = 0$ sier at en stav med lengde null er verdt ingenting, og det er det du trenger for å stoppe rekursjonen.

Legg merke til at «ikke kappe i det hele tatt» er med som et lovlig valg: $i = j$ gir $p_j + r_0 = p_j$ . Det er ikke en detalj — for enkelte prislister er hele staven faktisk best.

Stavkapping

n

Stavkapping-rekurrensen

r_j = \max_{1 \le i \le j}\big(p_i + r_{j-i}\big), \qquad r_0 = 0

📜Pseudokode-kontrakt: `Extended-Bottom-Up-Cut-Rod`

1. Antagelser om representasjon. Prislisten er p[1..n], indeksert fra 1, med p[i] som prisen for et stykke av lengde i. Alle lengder er heltall. To tabeller fylles: r[0..n] med inntektene og s[1..n] med valgene.

2. Pre-/postbetingelse. Før: n >= 0 og p[1..n] er gitt. Etter: r[j] er den største oppnåelige inntekten for en stav av lengde j, for hver j, og s[j] er lengden på det første stykket i en optimal oppdeling av j.

3. Pseudokoden.

Extended-Bottom-Up-Cut-Rod(p, n)
  Input:  prislisten p[1..n]
  Output: inntektstabellen r[0..n] og valgtabellen s[1..n]
  la r[0..n] og s[1..n] vaere nye tabeller
  r[0] = 0
  for j = 1 to n
      q = -uendelig
      for i = 1 to j
          if q < p[i] + r[j-i]
              q = p[i] + r[j-i]
              s[j] = i
      r[j] = q
  return r, s

Print-Cut-Rod-Solution(p, n)
  Input:  prislisten p og stavlengden n
  Output: lengdene i en optimal oppdeling
  (r, s) = Extended-Bottom-Up-Cut-Rod(p, n)
  while n > 0
      skriv ut s[n]
      n = n - s[n]

4. Invarianten i én setning. Før hver runde av den ytre løkka med telleverdi j inneholder r[0..j-1] de riktige optimalverdiene — derfor er hver r[j-i] den indre løkka slår opp i, allerede ferdig.

5. Kjøretid. Den indre løkka går j runder for hver j, så antall sammenligninger er $1 + 2 + \dots + n = n(n+1)/2$ , altså $\Theta(n^2)$ . Print-Cut-Rod-Solution gjør høyst n runder à konstant arbeid, altså $O(n)$ — rekonstruksjonen øker dermed ikke den asymptotiske kjøretiden.

✏️Eksempel 1: Åtte meter aluminium

Verkstedet har denne prislisten, i hundre kroner per stykke:

Lengde $i$	1	2	3	4	5	6	7	8
Pris $p_i$	4	10	16	18	21	24	29	39

Fyll tabellene

r

s

for

j = 1, \dots, 8

, og oppgi den beste inntekten for en åtte meters profil sammen med hvilken oppdeling som gir den.

Utfyllingen, lengde for lengde. For hver

j

sammenlignes kandidatene

p_i + r_{j-i}

for

i = 1, \dots, j

$j$	Kandidater $p_i + r_{j-i}$	$r_j$	$s_j$
1	$4+0=4$	4	1
2	$4+4=8$ , $10+0=10$	10	2
3	$4+10=14$ , $10+4=14$ , $16+0=16$	16	3
4	$4+16=20$ , $10+10=20$ , $16+4=20$ , $18+0=18$	20	1
5	$4+20=24$ , $10+16=26$ , $16+10=26$ , $18+4=22$ , $21+0=21$	26	2
6	$4+26=30$ , $10+20=30$ , $16+16=32$ , $18+10=28$ , $21+4=25$ , $24+0=24$	32	3
7	$4+32=36$ , $10+26=36$ , $16+20=36$ , $18+16=34$ , $21+10=31$ , $24+4=28$ , $29+0=29$	36	1
8	$4+36=40$ , $10+32=42$ , $16+26=42$ , $18+20=38$ , $21+16=37$ , $24+10=34$ , $29+4=33$ , $39+0=39$	42	2

r[0..8] = [0, 4, 10, 16, 20, 26, 32, 36, 42]

s[1..8] = [1, 2, 3, 1, 2, 3, 1, 2]

.
Rekonstruksjonen. Start på

n = 8

s[8] = 2

, så kapp av 2 meter og fortsett med 6.

s[6] = 3

, kapp av 3 og fortsett med 3.

s[3] = 3

, kapp av 3 og fortsett med 0. Ferdig.
Svaret:
- Beste inntekt: 42 (altså 4 200 kroner).
- Oppdelingen: 2 + 3 + 3.
Merk hva som skjer her. Å selge profilen hel gir bare

p_8 = 39

. Oppdelingen er verdt 3 mer, og det er ikke synlig fra prislisten uten å regne. Merk også at oppgaven ber om selve oppdelingen, ikke bare inntekten — uten valgtabellen

s

hadde du bare hatt tallet 42.
Når likhet oppstår, som ved

j = 4

der tre kandidater alle gir 20, låser pseudokoden seg på den første som ble funnet (

i = 1

). Det er et vilkårlig, men deterministisk valg: en annen tie-break gir en annen oppdeling med samme verdi, og begge er riktige svar.

📝Oppgave 1

Sjanger E

Oppgi kjøretiden til Extended-Bottom-Up-Cut-Rod på strammest mulig form, og skriv den ene setningen som begrunner den.

📝Oppgave 2

Eksamensnivå, sjanger C

En trelastbedrift har denne prislisten for planker:

Lengde $i$	1	2	3	4	5
Pris $p_i$	2	6	7	10	13

Oppgi tabellen

r[0..5]

og den optimale oppdelingen av en plank på 5 meter.

Lengste felles delsekvens (~20 min)

Når et redigeringsverktøy viser hva som er endret mellom to versjoner av en tekst, gjør det i praksis dette: det finner den lengste biten av innhold som står i begge versjoner, i samme rekkefølge, og markerer alt annet som lagt til eller fjernet. Den lengste felles biten trenger ikke være sammenhengende — hopper du over et avsnitt i midten, teller resten fortsatt med.

Det er problemet lengste felles delsekvens (longest common subsequence, LCS), og det er den mest brukte DP-malen i faget. Får du en oppgave om å sammenligne to sekvenser — tekst, gensekvenser, hendelseslogger, ruter — er dette mønsteret du gjenkjenner den mot.

Grepet er igjen å se på ett valg, og her er det det siste tegnet i hver sekvens. La $X = x_1x_2\dots x_m$ og $Y = y_1y_2\dots y_n$ , og la $c[i,j]$ være lengden på lengste felles delsekvens av de $i$ første tegnene i $X$ og de $j$ første i $Y$ . Da er det to tilfeller:

- Er $x_i = y_j$ , kan du ta med det tegnet, og resten av problemet er $c[i-1, j-1]$ .
- Er de forskjellige, kan ikke begge være med som siste tegn. Da må minst ett av dem droppes, og du tar det beste av å droppe $x_i$ eller å droppe $y_j$ .

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

Intuisjon: i det første tilfellet er det aldri dumt å ta med et tegn som matcher — det kan bevises med et bytteargument, og det er derfor rekurrensen ikke trenger å sammenligne med noe annet der. I det andre tilfellet vet vi bare at minst ett av de to tegnene ikke kan brukes som siste tegn, og da må begge muligheter prøves.

Tabellen har $(m+1)(n+1)$ celler og hver celle koster konstant tid, altså $\Theta(nm)$ .

Delsekvens

n

Lengste felles delsekvens (LCS)

\Theta(nm)

LCS-rekurrensen

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

📜Pseudokode-kontrakt: `LCS-Length`

1. Antagelser om representasjon. Sekvensene er X[1..m] og Y[1..n], indeksert fra 1. Verditabellen er c[0..m, 0..n] og retningstabellen b[1..m, 1..n]. Retningene skrives SKRA (opp til venstre), OPP og VENSTRE, og svarer til

\nwarrow

\uparrow

\leftarrow

i figuren under.

2. Pre-/postbetingelse. Før: m, n >= 0. Etter: c[i,j] er lengden på lengste felles delsekvens av X[1..i] og Y[1..j] for alle i, j, og b[i,j] peker på cellen den verdien kom fra. Svaret på hele problemet står i c[m,n].

3. Pseudokoden.

LCS-Length(X, Y)
  Input:  sekvensene X[1..m] og Y[1..n]
  Output: tabellene c[0..m, 0..n] og b[1..m, 1..n]
  la c[0..m, 0..n] og b[1..m, 1..n] vaere nye tabeller
  for i = 0 to m
      c[i, 0] = 0
  for j = 0 to n
      c[0, j] = 0
  for i = 1 to m
      for j = 1 to n
          if X[i] == Y[j]
              c[i, j] = c[i-1, j-1] + 1
              b[i, j] = SKRA
          else if c[i-1, j] >= c[i, j-1]
              c[i, j] = c[i-1, j]
              b[i, j] = OPP
          else
              c[i, j] = c[i, j-1]
              b[i, j] = VENSTRE
  return c, b

4. Invarianten i én setning. Når løkkene når celle (i, j), er alle tre cellene den leser — (i-1, j-1), (i-1, j) og (i, j-1) — allerede ferdig utfylt, fordi tabellen fylles rad for rad ovenfra og venstre mot høyre.

5. Kjøretid. Tabellen har $(m+1)(n+1)$ celler, og hver celle koster konstant tid: $\Theta(nm)$ . Plassbruken er også $\Theta(nm)$ når b skal beholdes til rekonstruksjon.

📜Pseudokode-kontrakt: `Print-LCS`

1. Antagelser om representasjon. Retningstabellen b er ferdig utfylt av LCS-Length, og X[1..m] er tilgjengelig. Rutinen kalles med i = m, j = n.

2. Pre-/postbetingelse. Før: b er fylt ut for alle celler med i >= 1 og j >= 1. Etter: rutinen har skrevet ut én lengste felles delsekvens, i riktig rekkefølge fra venstre mot høyre, og tabellene er urørt.

3. Pseudokoden.

Print-LCS(b, X, i, j)
  Input:  retningstabellen b, sekvensen X, og en celle (i, j)
  Output: en lengste felles delsekvens av X[1..i] og Y[1..j]
  if i == 0 or j == 0
      return
  if b[i, j] == SKRA
      Print-LCS(b, X, i-1, j-1)
      skriv ut X[i]
  else if b[i, j] == OPP
      Print-LCS(b, X, i-1, j)
  else
      Print-LCS(b, X, i, j-1)

4. Grunnideen i én setning. Hvert kall flytter seg minst ett hakk mot celle (0, 0), og skriver ut et tegn nøyaktig når retningen er SKRA — altså nøyaktig når de to tegnene matchet.

5. Kjøretid. Hvert kall reduserer i + j med minst 1, så antall kall er høyst $m + n$ , og hvert kall gjør konstant arbeid: $O(m+n)$ . Det er mindre enn $\Theta(nm)$ , så rekonstruksjonen øker ikke den asymptotiske kjøretiden — men den krever at b faktisk ble lagret.

✏️Eksempel 2: SPRANG mot PARKING

Finn lengste felles delsekvens av $X =$ SPRANG og $Y =$ PARKING. Fyll tabellen $c$ , oppgi lengden, og oppgi selve delsekvensen.

Tabellen $c$ (rader er SPRANG, kolonner er PARKING):

$j=0$	2 (A)	3 (R)	4 (K)	5 (I)	6 (N)	7 (G)
$i=0$	0	0	0	0	0	0	0
1 (S)	0	0	0	0	0	0	0
2 (P)	1	1	1	1	1	1	1
3 (R)	1	1	2	2	2	2	2
4 (A)	1	2	2	2	2	2	2
5 (N)	1	2	2	2	2	3	3
6 (G)	1	2	2	2	2	3	4

Retningstabellen $b$ , som er det rekonstruksjonen leser:

1 (P)	2 (A)	3 (R)	4 (K)	5 (I)	6 (N)	7 (G)
1 (S)	$\uparrow$	$\uparrow$	$\uparrow$	$\uparrow$	$\uparrow$	$\uparrow$	$\uparrow$
2 (P)	$\nwarrow$	$\leftarrow$	$\leftarrow$	$\leftarrow$	$\leftarrow$	$\leftarrow$	$\leftarrow$
3 (R)	$\uparrow$	$\uparrow$	$\nwarrow$	$\leftarrow$	$\leftarrow$	$\leftarrow$	$\leftarrow$
4 (A)	$\uparrow$	$\nwarrow$	$\uparrow$	$\uparrow$	$\uparrow$	$\uparrow$	$\uparrow$
5 (N)	$\uparrow$	$\uparrow$	$\uparrow$	$\uparrow$	$\uparrow$	$\nwarrow$	$\leftarrow$
6 (G)	$\uparrow$	$\uparrow$	$\uparrow$	$\uparrow$	$\uparrow$	$\uparrow$	$\nwarrow$

Rekonstruksjonen. Start i celle

(6,7)

, som er

\nwarrow

: G er med, gå til

(5,6)

. Der står

\nwarrow

: N er med, gå til

(4,5)

. Der står

\uparrow

: gå til

(3,5)

, som er

\leftarrow

— videre til venstre til

(3,3)

, som er

\nwarrow

: R er med, gå til

(2,2)

. Der står

\leftarrow

, videre til

(2,1)

, som er

\nwarrow

: P er med. Så er vi i

(1,0)

og stopper.
Tegnene skrives ut i den rekkefølgen kallene returnerer, altså framlengs — P, R, N, G.
Svaret:
- Lengde:

c[6,7] =

4.
- Lengste felles delsekvens: PRNG.
Merk at PRNG ikke står sammenhengende i noen av de to ordene — det er en delsekvens, ikke en delstreng. Merk også at hele rad 1 er null: S finnes ikke i PARKING i det hele tatt.

Kjøretid: $6 \cdot 7 = 42$ celler fylles, hver på konstant tid, altså $\Theta(nm)$ . Rekonstruksjonen bruker 9 kall, godt innenfor grensen $O(m+n) = O(13)$ .

Typiske feil

Å blande delsekvens med delstreng. En delsekvens trenger ikke være sammenhengende. LAK er en delsekvens av FLASKE, men ingen delstreng. Blander du dem, får du et helt annet — og enklere — problem, og feil rekurrens.

Av-én-feil i indeksene. Tabellen har rad 0 og kolonne 0, mens sekvensene er indeksert fra 1. Cellen $c[i,j]$ handler om X[1..i] og Y[1..j], altså om tegnene $x_i$ og $y_j$ — ikke om X[i+1]. Sjekk alltid det minste tilfellet: $c[1,1]$ skal være 1 hvis de to første tegnene er like, ellers 0.

Felle #6 — å påstå at rekonstruksjon fra en DP-tabell er «trivielt gratis». Verditabellen $c$ gir deg lengden, ikke sekvensen. Skal du ut med selve delsekvensen, må retningstabellen $b$ lagres — eller retningen leses tilbake ved å sammenligne nabocellene i $c$ . Det koster $O(m+n)$ , altså ingen asymptotisk økning, men leddet må stå i svaret.

Felle #7 — å blande pseudopolynomisk med NP-hardt. Den kommer for fullt i neste avsnitt: at 0-1-ryggsekk løses i $\Theta(nm)$ betyr verken at problemet er lett i teoretisk forstand, eller at det er bevist vanskelig.

Å tro at LCS er entydig. To ulike delsekvenser kan ha samme maksimale lengde. Retningstabellens tie-break avgjør hvilken du får ut, og et annet valg er like riktig.

📝Oppgave 3

Eksamensnivå, sjanger C

Finn lengste felles delsekvens av $X =$ LAKS og $Y =$ FLASKE. Oppgi tabellen $c$ og selve delsekvensen.

📝Oppgave 4

Eksamensnivå, sjanger F

Ta stilling til hver påstand.

a) Kjøretiden til LCS-Length er $\Theta(nm)$ uansett hvor mange tegn de to sekvensene har felles.
b) Vil du bare ha lengden på lengste felles delsekvens, klarer du deg med plass proporsjonal med den korteste sekvensen.
c) Bytter du om på hvilken sekvens som er $X$ og hvilken som er $Y$ , kan lengden bli en annen.

0-1-ryggsekk og hva pseudopolynomisk betyr (~20 min)

Du skal på en kajakktur og har plass til ni kilo i den vanntette pakksekken. Hver gjenstand har en vekt og en nytteverdi, og du kan ikke ta med en halv soveppose — enten er den med, eller så er den ikke. Hva pakker du?

Dette er 0-1-ryggsekkproblemet, og navnet kommer av nettopp den todelingen: hver gjenstand får verdien 0 eller 1, aldri noe imellom. Igjen ser vi på ett valg — gjenstand $i$ — og lar resten være et mindre delproblem:

- Lar du gjenstand $i$ ligge, har du de $i-1$ første gjenstandene og hele kapasiteten $j$ igjen.
- Tar du den med (mulig bare når $w_i \le j$ ), får du verdien $v_i$ pluss det beste du kan få av de $i-1$ første med kapasitet $j - w_i$ .

$K[i,j] = \begin{cases} 0 & \text{hvis } i = 0 \\ K[i-1,j] & \text{hvis } w_i > j \\ \max\big(K[i-1,j],\; v_i + K[i-1,\, j-w_i]\big) & \text{ellers}\end{cases}$

Intuisjon: delproblemet må ha to parametre. Med bare «de $i$ første gjenstandene» vet du ikke hvor mye plass som er brukt opp, og da kan du ikke avgjøre om gjenstand $i$ får plass. Restkapasiteten er den andre dimensjonen, og det er derfor tabellen blir todimensjonal.

Tabellen har $n$ rader og $m+1$ kolonner, hver celle koster konstant tid, altså $\Theta(nm)$ . Og her ligger fellen som gjør dette problemet interessant helt inn i Del 7.

0-1-ryggsekk

n

Ryggsekk-rekurrensen

i

✏️Eksempel 3: Ni kilo i pakksekken

Du har fem gjenstander og kapasitet $m = 9$ kilo:

$i$	Gjenstand	Vekt $w_i$	Verdi $v_i$
1	telt	5	12
2	sovepose	4	10
3	primus	3	6
4	kikkert	2	5
5	matpakke	1	2

Fyll tabellen

K

, oppgi den største oppnåelige verdien, og oppgi hvilke gjenstander som skal med. Sammenlign til slutt med det du ville fått ved å pakke grådig etter verdi per kilo.

Tabellen $K$ , én rad per gjenstand, én kolonne per kapasitet fra 0 til 9:

Rad $i$ / kapasitet $j$	1	2	3	4	5	6	7	8	9
0 (ingen)	0	0	0	0	0	0	0	0	0
1 (telt)	0	0	0	0	12	12	12	12	12
2 (sovepose)	0	0	0	10	12	12	12	12	22
3 (primus)	0	0	6	10	12	12	16	18	22
4 (kikkert)	0	5	6	10	12	15	17	18	22
5 (matpakke)	2	5	7	10	12	15	17	19	22

Rekonstruksjonen. Start i

K[5,9] = 22

og gå oppover. Er

K[i,j]

lik

K[i-1,j]

, ble gjenstand

i

ikke tatt; er de forskjellige, ble den tatt, og du trekker

w_i

fra kapasiteten.
-

K[5,9] = 22 = K[4,9]

: matpakken er ikke med.
-

K[4,9] = 22 = K[3,9]

: kikkerten er ikke med.
-

K[3,9] = 22 = K[2,9]

: primusen er ikke med.
-

K[2,9] = 22 \ne K[1,9] = 12

: soveposen er med. Ny kapasitet:

9 - 4 = 5

.
-

K[1,5] = 12 \ne K[0,5] = 0

: teltet er med. Ny kapasitet:

5 - 5 = 0

.
Svaret:

- Største verdi: 22.

- Pakkelisten: telt og sovepose, samlet vekt 9 kilo.
Sammenligningen med grådighet. Verdi per kilo er 2,4 for teltet, 2,5 for soveposen, 2,0 for primusen, 2,5 for kikkerten og 2,0 for matpakken. Pakker du grådig etter den rangeringen, tar du sovepose (4 kg), kikkert (2 kg) og primus (3 kg) — akkurat ni kilo — til en samlet verdi på $10 + 5 + 6 = 21$ . Det er dårligere enn 22, og det er et konkret moteksempel mot å løse 0-1-ryggsekk grådig.
Kjøretid: $n \cdot m = 5 \cdot 9 = 45$ celler i selve kjernen, hver på konstant tid, altså $\Theta(nm)$ . Rekonstruksjonen går én rad om gangen oppover, altså $O(n)$ , og øker ikke kjøretiden.

Nå til det som gjør dette problemet spesielt. Kjøretiden $\Theta(nm)$ ser polynomisk ut — det er et produkt av to tall fra oppgaven, ikke noe eksponentielt. Men det er den ikke, og forskjellen er verdt å bruke et par minutter på.

Når vi måler kjøretid i dette faget, måler vi den mot størrelsen på inputen. For et array med $n$ tall er $n$ en grei størrelse: arrayet består av $n$ elementer, så det tar plass proporsjonal med $n$ . Kapasiteten $m$ er noe helt annet. Den er ett tall, og et tall på $m$ skrives med omtrent $\lg m$ siffer. Skal du skrive kapasiteten 1 000 000, bruker du sju siffer — ikke en million.

Konsekvensen: en algoritme som bruker $\Theta(nm)$ tid, bruker tid som vokser eksponentielt i antall siffer i $m$ . Legger du til ett siffer på kapasiteten, blir problemet ti ganger så tungt, selv om inputen bare ble ett tegn lengre. Tabellen under er kjørt for et fast lite antall gjenstander:

Kapasitet $m$	Siffer i $m$	Celler $n \cdot m$ med $n = 3$
10	2	30
100	3	300
1 000	4	3 000
10 000	5	30 000
100 000	6	300 000

Det er dette som kalles pseudopolynomisk: polynomisk i tallverdiene, men ikke i lengden på inputen. Er kapasitetene små, er algoritmen helt utmerket i praksis — og det er nettopp derfor den brukes. Er de store, hjelper den ikke.
Hva dette IKKE betyr. At kjøretiden er pseudopolynomisk, er ikke et bevis for at problemet er vanskelig, og «pseudopolynomisk» er ikke et synonym for «NP-hardt». Det er en egenskap ved algoritmen, ikke en dom over problemet. Det motsatte forholdet gjelder heller ikke: at vi har en pseudopolynomisk algoritme, betyr ikke at problemet er lett. Skillet er felle #7 — å blande pseudopolynomisk og NP-hardt — og det er en av de feilene som oftest skiller riktig fra galt i Del 7. Samme skille gjelder Ford-Fulkerson i kap. 5.2, der kjøretiden avhenger av kapasitetenes størrelse på nøyaktig samme måte.

Pseudopolynomisk kjøretid

\Theta(nm)

Fraksjonell ryggsekk

Varianten der gjenstandene kan deles: du kan ta 40 % av en sekk sand og få 40 % av verdien. Til forskjell fra 0-1-varianten løses den grådig : sortér etter verdi per vektenhet, fyll med den beste først, og del den siste gjenstanden slik at sekken blir akkurat full. Algoritmen og bytteargumentet som viser at den er optimal, hører til kap. 6.4 . Kontrasten er poenget her: den lille endringen fra «hel eller ingenting» til «kan deles» flytter problemet fra dynamisk programmering til grådighet. På pakkelisten i Eksempel 3 ville den fraksjonelle varianten gitt 22,2 mot 0-1-variantens 22.

📝Oppgave 5

Sjanger D

Forklar med egne ord hva det betyr at kjøretiden $\Theta(nm)$ til 0-1-ryggsekk er pseudopolynomisk, og si i én setning hva begrepet ikke sier.

📝Oppgave 6

Eksamensnivå, sjanger C

Tre gjenstander skal pakkes i en sekk med kapasitet $m = 8$ :

$i$	Vekt $w_i$	Verdi $v_i$
1	3	9
2	4	10
3	5	12

Oppgi siste rad i tabellen

K

, den største oppnåelige verdien og hvilke gjenstander som velges.

📝Oppgave 7

Eksamensnivå, sjanger F

Ta stilling til påstandene. Ja eller nei først, deretter én setning.

a) Fordi 0-1-ryggsekk løses i $\Theta(nm)$ , er problemet løst i polynomisk tid.
b) Fraksjonell ryggsekk kan løses grådig.
c) Å ta gjenstandene i synkende verdi per vektenhet gir alltid optimal løsning på 0-1-ryggsekk.

📝Oppgave 8

Eksamensnivå, sjanger H

To turgrupper har hver ført dagbok over hvilke hytter de overnattet på, i den rekkefølgen de kom dit. Den ene lista har $m$ oppføringer, den andre $n$ . Turlaget vil vite den lengste rekkefølgen av hytter begge gruppene besøkte i samme rekkefølge, og vil ha selve hyttelista, ikke bare hvor lang den er. Gruppene kan ha vært på hytter den andre ikke besøkte, og de kan ha brukt ulikt antall dager.

Beskriv en algoritme. Svar i designformatet: hvilket klassisk problem dette er, paradigmet, konstruksjonen, rekonstruksjonen og kjøretiden.

Kjøretidene i dette kapitlet samlet

Algoritme	Beste	Verste	Forventet	Krav/egenskap
`Bottom-Up-Cut-Rod(p, n)`	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n^2)$	begge løkkene går alltid fullt ut; gir bare inntekten
`Extended-Bottom-Up-Cut-Rod(p, n)`	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n^2)$	fyller også valgtabellen `s`; nødvendig for å få oppdelingen
`Print-Cut-Rod-Solution(p, n)`	$O(n)$	$O(n)$	$O(n)$	krever utfylt `s`; øker ikke kjøretiden
`LCS-Length(X, Y)`	$\Theta(nm)$	$\Theta(nm)$	$\Theta(nm)$	alle celler fylles uansett innhold; $\Theta(nm)$ plass med `b`
`Print-LCS(b, X, m, n)`	$O(m+n)$	$O(m+n)$	$O(m+n)$	krever utfylt retningstabell `b`
`Knapsack-01(w, v, n, m)`	$\Theta(nm)$	$\Theta(nm)$	$\Theta(nm)$	pseudopolynomisk — $m$ er en tallverdi, ikke en telling
Fraksjonell ryggsekk	$O(n\lg n)$	$O(n\lg n)$	$O(n\lg n)$	grådig etter verdi per vektenhet; sorteringen dominerer (kap. 6.4)

De tre DP-radene følger samme regel: antall delproblemer ganger arbeidet per delproblem. Stavkapping har

n

delproblemer med voksende arbeid, altså en sum som gir

\Theta(n^2)

. LCS og ryggsekk har

nm

delproblemer med konstant arbeid, altså

\Theta(nm)

. Kan du de to regnestykkene, trenger du ikke pugge tallene.

Begrepsbank

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

`Extended-Bottom-Up-Cut-Rod`

r

`LCS-Length`

c

`Print-LCS`

b

Valgtabellen `s` i stavkapping

j

Inputstørrelse målt i bits

n

Delsekvens mot delstreng

En delsekvens bevarer rekkefølgen, men trenger ikke være sammenhengende. En delstreng må være sammenhengende. LAK er en delsekvens av FLASKE, men ikke en delstreng. LAS er også en delsekvens. ASK er en delstreng av FLASKE, og dermed også en delsekvens. Blander du dem, løser du feil problem: lengste felles delstreng har en annen rekurrens, og LCS-tabellen gir feil svar på det.

Hvorfor grådighet feiler på 0-1-ryggsekk

Fordi den beste gjenstanden per vektenhet kan blokkere en kombinasjon som fyller sekken bedre. Pakkelisten i Eksempel 3 viser det: grådig etter verdi per kilo velger sovepose, kikkert og primus til verdi 21, mens telt og sovepose gir 22. Uten muligheten til å dele gjenstander blir «restplassen» avgjørende, og den ser den grådige regelen ikke. Den fraksjonelle varianten har ikke problemet: der fylles restplassen alltid opp av en bit av neste gjenstand, og da er grådighet optimal.

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.