Recursive functions for dynamic programming problems

University of Bergen

23 October 2018

No git information available.

Recursive functions for dynamic programming problems

Javascript is disabled, please activate it to see correctly this post.

After learning about the dynamic programming approach to solve some algorithm problems. We realize that a recursive formulation of the solution is always crucial. This list is precisely a small compendium of such functions for some well-know algorithm problems.

0–1 Knapsack

Problem:
Maximize the sum of the values of the items in the knapsack so that the sum of the weights is less than or equal to the knapsack’s capacity.

Explicit Formulation:

Given

a set of $n$ items numbered from $1$ up to $n$,
each item has a weight $w_i$ and a value $v_i$ ,
the bag has a maximum weight capacity $W$.

$\begin{align*} \maximize &\sum_{i=1}^n v_i x_i \\ \st. &\sum_{i=1}^n w_i x_i \leq W\\ &x_i \in \{0,1\}. \end{align*}$

Here $x_i$ represents the number of instances of item $i$ to include in the knapsack.

Recursion:

Define $f(i,w)$ to be the maximum value that can be attained with weight less than or equal to $w$ using items up to $i$ (first $i$ items).

We can define $f(i,w)$ recursively as follows:

$\begin{align*} f(i, w) = \begin{cases} 0 &\text{if }i = 0,\\ f(i-1,\,w) &\text{if }w_i > w,\\ \max\{f(i-1,\,w),\,f(i-1,w-w_i)+v_i \} &\text{otherwise}. \end{cases} \end{align*}$

The solution can then be found by calling $f(n,W)$.

Variations:

bounded knapsack problem (BKP): $0\leq x_{i}\leq c$
unbounded knapsack problem (UKP): $x_{i}\geq 0$

3-partition

Problem:
Given integers $a_1, \cdots a_n$, we want to determine whether it is possible to partition of ${1,\cdots, n}$ into three disjoint subsets $I$ , $J$, $K$ such that

$\begin{equation*} \sum_{i\in I} a_i = \sum_{j\in J} a_j = \sum_{k\in K} a_k = \frac{1}{3}\sum_{i=1}^n a_i. \end{equation*}$

Recursion:

Assume that $S = \sum_{i=1}^n a_i$ is divisible by $3$, otherwise we can’t make such a partition.

For this decision problem, we define $f(i, p, q)$ to be $\true$ if we are able to find two disjoint sets $I$ and $J$ such that each sum $p$ and $q$ respectively with the first $i$ items available.

$$\begin{align*} \sum_{i\in I} a_i &= p,\\ \sum_{j\in J} a_j &= q,\\ I \sqcup J &= \{1, \cdots, m\}. \end{align*}$$

The recursive formulation of the solution is as follows:

$\begin{align*} f(i, p, q) = \begin{cases} \true &\text{if }i = p = q = 0,\\ \false &\text{if }i = 0 \\ \underbrace{f(i-1,p - a_i, q)}_{i\in I \and i\not\in J} \or \underbrace{f(i-1,p, q-a_i)}_{i\not\in I \and i\in J} \} \or \underbrace{f(i-1,p, q)}_{i\not\in I \and i\not \in J \and i \in K} \} &\text{otherwise}. \end{cases} \end{align*}$

The answer then can be found by computing $f(n, \frac{S}{3}, \frac{S}{3})$. The sets $I$ and $J$ can be found by using an auxiliary array to register if which set we put each element.

Sequence alignment

Find the highest cost for an alignment of two strings $x$ and $y$ based on a scoring matrix $\delta$ of $(N+1\times N+1)$ where $N$ is the size of the alphabet with an extra character - for gaps.

An alignment is a way of matching up the two strings. It also needs to follow the rules:

The characters of each string must appear in order in the align
Each column of the alignment must contain a character from at least one of the strings

Recursion:

Define $f(i,j)$ to be the maximum score for an alignment that can be obtained when we attempt to align the strings $x$, $y$ in one of three possible ways in the following. The gaps are represented by -.

$\begin{align*} x_i&\cdot \cdots x_{n}\\ y_j&\cdot \cdots. \\[3mm] x_i&\cdot \cdots \cdot \cdot \cdots x_{n}\\ -&\cdot \cdots \cdot y_j\cdot \cdots. \\[3mm] -&\cdot \cdots \cdot x_i\cdot \cdots \cdot x_{n}\\ y_j&\cdot \cdots \cdot \cdots.\\ \end{align*}$

We can define $f(i,j)$ recursively as follows, moving us from left to right with the strings to respect their order. The first argument $i$ is about the position in the string $x$, and the argument $j$ is about the position in the string $y$ in the following definition.

$\begin{align*} f(i, j) = \begin{cases} 0 &\text{ if } i > n \and j > m, \\ \max \begin{cases} \delta(x_i,y_i) + f(i+1,j+1) &\text{if } i \leq n \and j \leq m,\\ \delta(x_{i},-) + f(i+1, j) &\text{if } i \leq n, \\ \delta(-,y_{j}) + f(i, j+1) &\text{if } j \leq m \end{cases} &\text{ otherwise.} \end{cases} \end{align*}$

The solution can then be found by calling $f(1,1)$.

Maximum sum of a contiguous subsequence

Let $S = [s_1 ,s_2 ,\cdots,s_n]$ be a sequence of integers.

A contiguous subsequence of $S$ consists of consecutive elements of S. We want to find a contiguous subsequence of $S$ that has the maximum sum.

Recursion:

Define $f(i)$ to be the maximum subsequence from the beginning to the $i$-position.

$\begin{align*} f(i) = \begin{cases} s_1 &\text{ if } i = 1, \\ \max \{ f(i-1) + s_i, f(i-1) \} &\text{ otherwise. } \end{cases} \end{align*}$

This problem is also known as Maximum subarray problem (Kadane’s algorithm).

Edit distance

Problem:
Given two strings $x$ and $y$ on an alphabet Σ, the edit distance or also called levenshtein distance between $x$ and $y$ is the minimum-weight series of edit operations that transforms $x$ into $y$. The operations available are insertion, deletion, and substitution. The cost for all these operations is given by the functions $w_\mathrm{ins}$,$w_\mathrm{del}$ and $w_\mathrm{subs}$ respectively.

Recursion:
The edit distance between of $x = x_1\ldots x_n$ and $y = y_1\ldots y_m$ is given by the recurrence $f(n,m)$ defined as follows.

$\begin{align*} f(i,j) = \begin{cases} \sum_{k=1}^{i} w_\mathrm{del}(x_{k}) &\text{ if } 1 \leq i \leq m \and j = 0,\\ \sum_{k=1}^{j} w_\mathrm{ins}(y_{k}) &\text{ if } 1 \leq j \leq m \and i = 0,\\ \min \begin{cases} f(i-1, j-1) &\text{ if } x_i = x_j,\\ f(i-1, j-1) + w_\mathrm{subs}(a_{i}, b_j) &\text{ fix } x_i,\\ f(i-1, j) + w_\mathrm{del}(a_{i}) &\text{ delete }x_i, \\ f(i, j-1) + w_\mathrm{ins}(b_{j}) &\text{ insert }y_j. \\ \end{cases} & \text{ otherwise .} \end{cases} \end{align*}$

The edit distance is found by calling $f(n,m)$ for the given strings $x$ and $y$.

Raw Edit History Print Send Mail

Blog

Recursive functions for dynamic programming problems

Recursive functions for dynamic programming problems

0–1 Knapsack

3-partition

Sequence alignment

Maximum sum of a contiguous subsequence

Edit distance