Oppgave o i eksamen 2012 ber deg dele en heltallstabell \(A\) i (sammenhengende, ikke-tomme, ikke-overlappende) segmenter, så hvert segment summerer til et av tallene i en annen heltallstabell \(B\). Løsningsforslaget gir en forklaring (i tillegg til pseudokode), men den er kanskje litt knapp for enkelte.

Fra løsningsforslaget:

Løses vha. dynamisk programmering, der vi har en boolsk tabell \(T\), slik at \(T[k]\) er sann hvis og bare hvis det finnes en partisjon for de \(k\) første elementene.

Pseudokoden viser hvordan man kan beregne \(T\), men for å skjønne hvordan den fungerer, må man naturligvis skjønne dynamisk programmering, eller dekomponering mer generelt. Tanken er som alltid:

  1. Se din spesifikke input som én av en familie med instanser
  2. Finn ut hvordan disse instansene bygger på hverandre

Vi har et beslutningsproblem, og instansen vår er som følger:

Input: Heltallstabeller \(A\) og \(B\)
Spørsmål: Kan \(A\) partisjoneres i segmenter som summerer til tall i \(B\)?

Det er flere måter vi kan dekomponere denne instansen på, naturligvis, og mange av dem kunne nok gi andre algoritmer – men i løsningsforslaget har vi valgt å parametrisere familien vår med en lengde \(k\), som gir oss et prefiks av \(A\). Dette er den samme dekomponeringen vi bruker f.eks. i Insertion-Sort, Cut-Rod og (for to sekvenser) LCS. På sett og vis bruker vi den samme ideen også i Floyd-Warshall (der sekvensen er en vilkårlig ordning av nodene) og Knapsack (der sekvensen er en vilkårlig ordning av objektene). Det er i det hele tatt en dekomponeringsidé det er lurt å notere seg bak øret!

La \(n\) være lengden til \(A\). Familien vår blir da en serie med instanser, én for hver \(k\), der \(1\leq k\leq n\):

Input: Heltallstabeller \(A[1\mkern1mu.\mkern1mu.\mkern1mu k]\) og \(B\)
Spørsmål: Kan \(A[1\mkern1mu.\mkern1mu.\mkern1mu k]\) partisjoneres i segmenter som summerer til tall i \(B\)?

Forenklet kan vi tenke på de ulike prefiksene \(A[1\mkern1mu.\mkern1mu.\mkern1mu k]\) som delinstansene. Den opprinnelige instansen får vi naturligvis for \(k=n\).

Så da har vi familien vår med delinstanser, men vi har ikke definert noen delinstans-relasjon – vi vet ikke hvilke instanser som bygger på hvilke, og hvordan.

Cluet her er at vi skal splitte tabellen i segmenter, og når vi jobber induktivt vil vi gjerne se på de siste trinnet, som her blir det siste segmentet. Det siste segmentet blir altså den biten vi kutter av på slutten, og den kan ha ulike lengder – som gjør at vi trenger å løse ulike delinstanser rekursivt. Med andre ord bestemmer vi oss for at \(A[1\mkern1mu.\mkern1mu.\mkern1mu i]\) skal være en delinstans av \(A[1\mkern1mu.\mkern1mu.\mkern1mu j]\) hvis og bare hvis \(i < j\), akkurat som f.eks. i Cut-Rod.

Og akkurat som i Cut-Rod så prøver vi oss på å klippe av biter av ulik lengde fra slutten, i en løkke. For hver lengde \(\ell\) får vi altså vi følgende to spørsmål som må besvares:

  1. Finnes summen av \(A[(k-\ell+1)\mkern1mu.\mkern1mu.\mkern1mu k]\) i \(B\)?
  2. Kan \(A[1\mkern1mu.\mkern1mu.\mkern1mu k-\ell]\) partisjoneres i segmenter som summerer til tall i \(B\)?

Det første kan vi besvare effektivt dersom vi lager oss f.eks. en hashtabell av tallene i \(B\). Om vi også summerer verdiene etter hvert som vi øker lengden på det siste segmentet, så kan hele operasjonen utføres i konstant tid.

Det andre spørsmålet er jo bare én av delinstansene våre, og dem antar vi jo at vi alt har løst – så der kan vi bare slå opp svaret (evt. regne det ut rekursivt).

Svaret for hver delinstans \(k\) lagrer vi altså i en boolsk tabell \(T\), og så ender vi med f.eks. en iterativ løsning som den i løsningsforslaget