Sist endret: 23.09.2016

Løsningsforslag - Dynamisk programmering

Innleveringsfrist: 09.10.2017 15:00

Du er logget inn og får derfor se om du har svart riktig/feil på de enkelte oppgavene.
LF-svar er markert med grønt og feil svar er markert med rødt.

Hvis dere er uenige i fasit, oppfordres dere til å diskutere dette på Piazza.

Oppgave 1

a) Hva innebærer overlappende delproblemer? (5 %)

At delproblemene er praktisk talt like, og derfor trygt kan ignoreres

At delproblemene blir løst i konstant tid

At samme delproblem må løses flere ganger av en rekursiv algoritme

Ingen av delene

Din kommentar:
LF-forklaring:

b) Hvilket av disse problemene er hensiktsmessig å løse med dynamisk programmering? (5 %)

Finne et element som forekommer mer enn én gang i en liste bestående av n heltall mellom 1 og n-1.

Sortere en liste bestående av n heltall mellom 1 og n².

Finne det n'te Fibonacci tallet

Finne det elementet i et binært søketre som har verdi nærmest en oppgitt verdi.

Din kommentar:
LF-forklaring:	Problemet med å finne det n'te Fibonacci tallet har overlappende delproblemer.

c) Når er det hensiktsmessig å bruke dynamisk programmering? (5 %)

Når vi kan rekursivt løse problemet

Når problemet har optimal substruktur

Når delproblemene overlapper

Når vi kan løse problemet med "top down approach"

Din kommentar:
LF-forklaring:

Oppgave 2

I denne oppgaven skal vi ta for oss et rektangulært rutenett gitt som følger:

Vi skal nå prøve å finne ut av hvor mange veier det finnes fra punkt start (punkt [1, 1]) til punkt Mål (punkt [m, n]) under visse restriksjoner.
En lovlig vei fra Start til Mål defineres ved at et skritt fra punkt [i, j] på veien skal gå enten til punktet [i+1, j] eller til punktet [i, j+1]. To veier er forskjellige dersom de ikke er identisk like, skritt for skritt.
Funksjonen T(i, j) skal gi antall veier fra punkt [1, 1] til punkt [i, j]. Dette fører til at T(1, 2) = 1 og T(3, 2) = 3.

a) Hva blir T(1, 4) ? (10 %)

Din kommentar:
LF-forklaring:

b) Hva blir T(4, 3)?(Det kan være lurt å prøve å finne et system for ? svare p? oppgaven) (15 %)

Din kommentar:
LF-forklaring:

c) Finn et uttrykk som gjør deg i stand til å regne ut T(m, n). T(m, n) = ? (35 %)

T(m-1, n-1) + 2

MAX{ T(m-1, n), T(m, n-1) } + 1

T(m-1, n) + T(m, n-1)

m² + n² - m * n

T(m-1, n) + T(m, n-1) + T(m-1, n-1)

Din kommentar:
LF-forklaring:	Merk at du også må ha med sluttbetingelsen T(1,1) = 1 for å faktisk regne ut T(m,n). Men T(m-1,n) + T(m,n-1) er det eneste av uttrykkene som gjør deg i stand til å regne ut T(m,n), uavhengig av sluttbetingelse.

Oppgave 3

Stavkutting problemet
Gitt en stav med lengde n. En stav med lengde i kan selges for p_i, for i=1,2,...,n. Finn hvordan staven skal kuttes opp slik at du maksimerer inntekten R ved å selge staven.
Hva blir R gitt:

a)
N=4
p₁ = 4, p₂ = 9, p₃ = 15, p₄ = 18 (5 %)

Din kommentar:
LF-forklaring:	Hvis den deles slik at en del har lengde i = 3, og den andre lengde i = 1. Får R = 19

b)
N=8
p₁ = 4, p₂ = 9, p₃ = 15, p₄ = 18, p₅ = 21, p₆ = 28, p₇ = 31, p₈ = 37 (5 %)

Din kommentar:
LF-forklaring:	Deles i lengder 3, 3 og 2. R = 39

c) Hvor mange delproblemer må man løse for å finne optimal løsning for stavkutting problemet? (5 %)

$\Theta(lgn)$

$\Theta(n)$

$\Theta(n^2)$

$\Theta(2^n)$

Din kommentar:
LF-forklaring:

Oppgave 4

Ryggsekkproblemet:
Gitt n elementer med vekt w₁,...,w_n og verdi v₁,...,v_n og en ryggsekk med kapasitet W, finn den mest verdifulle kombinasjonen av elementer du får plass til i sekken. V er da den totale verdien av denne kombinasjonen.

Hva blir V gitt:

a) W = 5
v₁ = 12, v₂ = 10, v₃ = 20, v₄ = 15
w₁ = 2, w₂ = 1, w₃ = 3, w₄ = 2
(5 %)

Din kommentar:
LF-forklaring:

b) W = 740
v₁ = 18, v₂ = 27,v₃ = 51, v₄ = 36, v₅ = 24, v₆ = 22, v₇ = 29, v₈ = 10, v₉ = 24, v₁₀ = 40
w₁ = 320, w₂ = 301, w₃ = 371, w₄ = 296, w₅ = 303, w₆ = 359, w₇ = 148, w₈ = 275, w₉ = 296, w₁₀ = 395
(5 %)

Din kommentar:
LF-forklaring: