28.2 A first DP algorithm¶

Part 3 · Dynamic programming · Chapter 28 · Chapter 28: Rod cutting (RCP) · Lecture notes, volume 3 (PDF) · Slides · Exercises: Rod cutting (RCP)

Step 1: computation of the optimal value

For any $\ell \in \{0,1,\dots,n\}$, let $v(\ell)$ be the optimal value of the RCP subinstance given by:

a rod of length $\ell$,
a set $\{1,2,\dots,\ell\}$ of $\ell$ possible piece lengths,
for each piece length $j \in \{1,2,\dots,\ell\}$, a profit $p_j$.

The recursive formula to compute $v(\ell)$ reads as follows:

\[\begin{equation*} \label{eq:1} v(\ell)= \left\{ \begin{array}{ll} \displaystyle \max \bigg\{ p_j + v(\ell-j) : j \in \{1,2,\dots,\ell\}\bigg\} & \textrm{if $1\le \ell \le n$,}\\[2ex] 0 & \textrm{if $\ell=0$.} \end{array} \right. \tag{28.1} \end{equation*}\]

The recursive decomposition process of formula $\eqref{eq:1}$ generates $\ell$ independent subproblems, each corresponding to a possible choice of cutting a first piece of length $j$ from a rod of length $\ell$. Here, $v(0)=0$ since a rod of length $0$ cannot be cut and has profit $0$.
The optimal value $v(\ell)$ is obtained by trying all possible first-piece lengths and selecting the one that maximizes the sum $p_j+v(\ell-j)$ of the profit of the first piece and the optimal value of the residual subproblem.
Hence, an optimal solution for a rod of length $\ell$ is built by combining the chosen first piece of length $j$ with an optimal solution of the residual subproblem of length $\ell-j$.

$\rightsquigarrow$ Optimal Substructure verified!
Different choices of the first-piece length, possibly made for different values of $\ell$, can lead to the same residual length, and therefore the same value $v(\ell)$ may need to be computed several times during the recursive evaluation of formula $\eqref{eq:1}$.

$\rightsquigarrow$ Overlapping Subproblems verified!
A first method to compute the optimal value $v(n)$ of the RCP instance is the top-down approach. The method starts from the call with $\ell=n$ and evaluates formula $\eqref{eq:1}$ recursively: each call for a rod of length $\ell$ triggers further calls for rods of length $\ell-j$, for all $j \in \{1,2,\dots,\ell\}$, until the base case $v(0)$ is reached.
The recursion tree of the function $v$ has one node for each recursive call, labeled with the function call it represents. The root represents the initial call. The children of a node represent the recursive calls made by that call. The leaf nodes represent the base cases.

Example 28.3: Recursion tree

We consider the RCP instance of Example 28.1. This is the recursion tree of the top-down approach to compute $v(4)$:

The function $v$ is called $16$ times, and the same subproblems are solved multiple times: $v(2)$ is called $2$ times, $v(1)$ is called $4$ times, and $v(0)$ is called $8$ times. All the other calls are made only once.
The value $v(\ell)$, for a generic rod length $\ell$, can be computed once the values $v(j)$ are known for all smaller lengths $j<\ell$.
Example 28.4: Computing the values of the $v$ function

We consider the RCP instance of Example 28.1 with a rod of length $n = 4$ and the profits associated with the possible piece lengths are:

\[ \begin{array}{l|rrrrrrr} \hline & {\ell = 1} & {\ell = 2} & {\ell = 3} & {\ell = 4} \\ \hline {p_\ell} & {1} & {5} & {8} & {9} \\ \hline \end{array} \]

The value of the function $v$ can be computed by starting from the base case $v(0)=0$ and then computing the values of $v(1)$, $v(2)$, $v(3)$, and $v(4)$ in order, as follows:
- Since we know the value of $v(0)$, we can compute $v(1)$, as follows:
  
  \[ v(1)=p_1 + v(0) = 1 + 0 = 1 \]
- Once we have computed $v(1)$, we can compute $v(2)$, as follows:
  
  \[ v(2)= \max\{p_1+v(1),p_2+v(0)\} = \max\{1+1,5+0\} = 5 \]
- Once we have computed $v(2)$ and $v(1)$, we can compute $v(3)$, as follows:
  
  \[ v(3)= \max\{p_1+v(2),p_2+v(1),p_3+v(0)\} = \max\{1+5,5+1,8+0\} = 8 \]
- Once we have computed $v(3)$, $v(2)$ and $v(1)$, we can compute $v(4)$, as follows:
  
  \[\begin{align*} v(4)&= \max\{p_1+v(3),p_2+v(2),p_3+v(1),p_4+v(0)\}\\ &= \max\{1+8,5+5,8+1,9+0\} = 10 \end{align*}\]
We can avoid solving the same subproblems repeatedly by storing the value of each subproblem as soon as it is computed. The values are stored in a lookup table.
Since solving a subproblem with value $v(\ell)$ depends only on subproblems with values $v(j)$, with $j<\ell$, we can solve the subproblems for increasing values of $\ell$, starting from the base case $v(0)=0$ and building up to $v(n)$: this observation naturally leads to a much more efficient method to compute the optimal value $v(n)$ of the RCP instance.

A second method to compute the optimal value $v(n)$ of the RCP instance is the bottom-up approach. The method starts from the base case $v(0)=0$ and evaluates formula $\eqref{eq:1}$ for increasing rod lengths $\ell \in \{1,2,\dots,n\}$: each value $v(\ell)$ is computed using the already-computed values $v(0), v(1), \dots, v(\ell-1)$, until the value $v(n)$ of the RCP instance is obtained.

This is the pseudo-code of the DP algorithm using the bottom-up approach:

Algorithm: DP1

Input: An RCP instance given by the length $n$ of the rod and an array $p[1..n]$ of piece profits

Output: The optimal value of the RCP instance

1Function DP1($n,p$)

2${v} := \textnormal{new array}[0..n]$

3${v}[0] \leftarrow 0$

4for $\ell := 1$ to $n$ do

5$\mathit{m} := 0$

6for $j := 1$ to $\ell$ do

7if $\mathit{m} < p[j] + {v}[\ell-j]$ then

8$\mathit{m} \leftarrow p[j] + {v}[\ell-j]$

9end

10end

11${v}[\ell] \leftarrow \mathit{m}$

12end

13return ${v}[n]$

The vector ${v}[0..n]$ is the lookup table: it stores the optimal values of all subproblems, with the base case ${v}[0]=0$.
The outer loop, over $\ell \in \{1,2,\dots,n\}$, computes ${v}[\ell]$ in increasing order of rod length.
The inner loop, over $j \in \{1,2,\dots,\ell\}$, evaluates all possible first-piece lengths and keeps in $\mathit{m}$ the largest value $p[j]+{v}[\ell-j]$.
At the end of the inner loop, ${v}[\ell] \leftarrow \mathit{m}$ stores the optimal value ${v}[\ell]$.
Finally, the optimal value ${v}[n]$ of the RCP instance is returned.

Example 28.5: Execution of the DP algorithm

We consider the RCP instance of Example 28.1 with a rod of length $n = 4$ and the profits associated with the possible piece lengths are:

\[ \begin{array}{l|rrrrrrr} \hline & {\ell = 1} & {\ell = 2} & {\ell = 3} & {\ell = 4} \\ \hline {p_\ell} & {1} & {5} & {8} & {9} \\ \hline \end{array} \]

For each step of the DP algorithm, the table shows the values of $\ell$ and $j$, the current value of $\mathit{m}$, and the cell ${v}[\ell]$. The cell of $\mathit{m}$ is highlighted in red when updated; the cell of ${v}[\ell]$ is highlighted in blue when assigned.

$\ell$	$j$	${v}[\ell]$	$\mathit{m}$	Action
$-$	$-$	0	$-$	${v}[0]\leftarrow 0$
	$-$	$-$	0	$\mathit{m}\leftarrow 0$
1	1	$-$	1	$p[1]{+}{v}[0]=1{+}0=1>0$: $\mathit{m}\leftarrow 1$
	$-$	1	1	${v}[1]\leftarrow \mathit{m}=1$
	$-$	$-$	0	$\mathit{m}\leftarrow 0$
2	1	$-$	2	$p[1]{+}{v}[1]=1{+}1=2>0$: $\mathit{m}\leftarrow 2$
	2	$-$	5	$p[2]{+}{v}[0]=5{+}0=5>2$: $\mathit{m}\leftarrow 5$
	$-$	5	5	${v}[2]\leftarrow \mathit{m}=5$
	$-$	$-$	0	$\mathit{m}\leftarrow 0$
3	1	$-$	6	$p[1]{+}{v}[2]=1{+}5=6>0$: $\mathit{m}\leftarrow 6$
	2	$-$	6	$p[2]{+}{v}[1]=5{+}1=6=\mathit{m}$: no update
	3	$-$	8	$p[3]{+}{v}[0]=8{+}0=8>6$: $\mathit{m}\leftarrow 8$
	$-$	8	8	${v}[3]\leftarrow \mathit{m}=8$
	$-$	$-$	0	$\mathit{m}\leftarrow 0$
4	1	$-$	9	$p[1]{+}{v}[3]=1{+}8=9>0$: $\mathit{m}\leftarrow 9$
	2	$-$	10	$p[2]{+}{v}[2]=5{+}5=10>9$: $\mathit{m}\leftarrow 10$
	3	$-$	10	$p[3]{+}{v}[1]=8{+}1=9<10$: no update
	4	$-$	10	$p[4]{+}{v}[0]=9{+}0=9<10$: no update
	$-$	10	10	${v}[4]\leftarrow \mathit{m}=10$

This is the vector ${v}$ after the execution of the DP algorithm:

\[ \begin{array}{c|ccccc} \hline & {\ell = 0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} \\ \hline {{v}[\ell]} & 0 & 1 & 5 & 8 & 10 \\ \hline \end{array} \]

After the execution of the DP algorithm, the vector ${v}$ contains the optimal value ${v}[\ell]$ for every rod length.

Step 2: computation of an optimal solution

To compute an optimal solution, it is necessary to store some additional information.
For each rod length $\ell$, in addition to the optimal value ${v}[\ell]$, we store ${s}[\ell]$, the size of the first piece to cut off in an optimal solution for a rod of length $\ell$.

Starting from $\ell=n$, the value ${s}[\ell]$ gives the length of the first piece to cut; the remaining rod has length $\ell-{s}[\ell]$, and the same rule can be applied again, and so on, until the residual length reaches $0$.

This is the pseudo-code of the DP algorithm using the bottom-up approach with the storing of the information necessary to compute an optimal solution:

Algorithm: DP1_InfoSol

Input: An RCP instance given by the length $n$ of the rod and an array $p[1..n]$ of piece profits

Output: The optimal value of the RCP instance and the information vector ${s}[1..n]$

1Function DP1_InfoSol($n,p$)

2${v} := \textnormal{new array}[0..n]$

3${s} := \textnormal{new array}[1..n]$

4${v}[0] \leftarrow 0$

5for $\ell := 1$ to $n$ do

6$\mathit{m} := 0$

7$\mathit{t} := 0$

8for $j := 1$ to $\ell$ do

9if $\mathit{m} < p[j] + {v}[\ell-j]$ then

10$\mathit{m} \leftarrow p[j] + {v}[\ell-j]$

11$\mathit{t} \leftarrow j$

12end

13end

14${v}[\ell] \leftarrow \mathit{m}$

15${s}[\ell] \leftarrow \mathit{t}$

16end

17return ${v}[n], {s}$

The DP algorithm uses the additional temporary variable $\mathit{t}$ to keep track of the decision made when $\mathit{m}$ is updated. If a first piece of length $j$ is selected, $\mathit{t}\leftarrow j$ stores this decision. At the end of the inner loop, ${s}[\ell]\leftarrow \mathit{t}$ stores the length of the selected first piece, together with the optimal value ${v}[\ell]\leftarrow \mathit{m}$.

Example 28.6: Computation of the additional information

We consider the RCP instance of Example 28.1 with a rod of length $n = 4$ and the profits associated with the possible piece lengths are:

\[ \begin{array}{l|rrrrrrr} \hline & {\ell = 1} & {\ell = 2} & {\ell = 3} & {\ell = 4} \\ \hline {p_\ell} & {1} & {5} & {8} & {9} \\ \hline \end{array} \]

For each step of the DP algorithm, the table shows the values of $\ell$ and $j$, the cell ${s}[\ell]$, the current value of $\mathit{m}$, and the current value of $\mathit{t}$. The cell of $\mathit{m}$ is highlighted in red when updated; the cell of $\mathit{t}$ and the cell of ${s}[\ell]$ are highlighted in blue when updated.

$\ell$	$j$	${s}[\ell]$	$\mathit{m}$	$\mathit{t}$	Action
$-$	$-$	$-$	$-$	$-$	Initial state
	$-$	$-$	0	0	$\mathit{m}\leftarrow 0$, $\mathit{t}\leftarrow 0$
1	1	$-$	1	1	$1{+}0=1>0$: $\mathit{m}\leftarrow 1$, $\mathit{t}\leftarrow 1$
	$-$	1	1	1	${v}[1]\leftarrow \mathit{m}=1$, ${s}[1]\leftarrow \mathit{t}=1$
	$-$	$-$	0	0	$\mathit{m}\leftarrow 0$, $\mathit{t}\leftarrow 0$
2	1	$-$	2	1	$1{+}1=2>0$: $\mathit{m}\leftarrow 2$, $\mathit{t}\leftarrow 1$
	2	$-$	5	2	$5{+}0=5>2$: $\mathit{m}\leftarrow 5$, $\mathit{t}\leftarrow 2$
	$-$	2	5	2	${v}[2]\leftarrow \mathit{m}=5$, ${s}[2]\leftarrow \mathit{t}=2$
	$-$	$-$	0	0	$\mathit{m}\leftarrow 0$, $\mathit{t}\leftarrow 0$
3	1	$-$	6	1	$1{+}5=6>0$: $\mathit{m}\leftarrow 6$, $\mathit{t}\leftarrow 1$
	2	$-$	6	1	$5{+}1=6=\mathit{m}$: no update
	3	$-$	8	3	$8{+}0=8>6$: $\mathit{m}\leftarrow 8$, $\mathit{t}\leftarrow 3$
	$-$	3	8	3	${v}[3]\leftarrow \mathit{m}=8$, ${s}[3]\leftarrow \mathit{t}=3$
	$-$	$-$	0	0	$\mathit{m}\leftarrow 0$, $\mathit{t}\leftarrow 0$
4	1	$-$	9	1	$1{+}8=9>0$: $\mathit{m}\leftarrow 9$, $\mathit{t}\leftarrow 1$
	2	$-$	10	2	$5{+}5=10>9$: $\mathit{m}\leftarrow 10$, $\mathit{t}\leftarrow 2$
	3	$-$	10	2	$8{+}1=9<10$: no update
	4	$-$	10	2	$9{+}0=9<10$: no update
	$-$	2	10	2	${v}[4]\leftarrow \mathit{m}=10$, ${s}[4]\leftarrow \mathit{t}=2$

This is the vector ${s}$ after the execution of the DP algorithm:

\[ \begin{array}{c|cccc} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} \\ \hline {{s}[\ell]} & 1 & 2 & 3 & 2 \\ \hline \end{array} \]

Once the vector ${s}$ has been computed, an optimal solution of the RCP instance can be computed by repeatedly applying the following rule, starting from $j=n$ and $x_{\ell}=0$ for all $\ell \in \{1,2,\dots,n\}$:

\[ x_{{s}[j]} \leftarrow x_{{s}[j]}+1, \qquad j \leftarrow j-{s}[j], \]

until $j=0$. This yields the vector $(x_1,x_2,\dots,x_n)$, where each entry $x_{\ell}$ is the number of pieces of length $\ell$ in an optimal solution.

The following pseudo-code implements the computation of an optimal solution, given the vector ${s}$.

Algorithm: DP1_SolComputation

Input: The rod length $n$ of the RCP instance and the vector ${s}[1..n]$

Output: An optimal solution of the RCP instance

1Function DP1_SolComputation($n,{s}$)

2$x := \textnormal{new array}[1..n]$

3for $\ell := 1$ to $n$ do

4$x[\ell] \leftarrow 0$

5end

6$j := n$

7while $j > 0$ do

8$x[{s}[j]] \leftarrow x[{s}[j]]+1$

9$j \leftarrow j - {s}[j]$

10end

11return $x$

Example 28.7: Computing an optimal solution

After the execution of the DP algorithm on the instance of Example 28.1, we have the following vector ${s}$:

\[ \begin{array}{l|rrrr} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} \\ \hline {{s}[\ell]} & 1 & 2 & 3 & 2 \\ \hline \end{array} \]

We can compute an optimal solution for a rod of length $n=4$ as follows:

Iteration	$j$	${s}[j]$	$x[2]$	$j \leftarrow j-{s}[j]$
$-$	$-$	$-$	0	$j=4$
$1$	$4$	$2$	1	$j=4-2=2$
$2$	$2$	$2$	2	$j=2-2=0$

An optimal solution is the vector:

\[ (0,2,0,0) \]

The same computation procedure, based on the vector $s$, can be applied starting from any rod length $\ell$.

Example 28.8: Computing optimal solutions for rod lengths 3 and 2

After the execution of the DP algorithm on the instance of Example 28.1, we have the following vector ${s}$:

\[ \begin{array}{l|rrrr} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} \\ \hline {{s}[\ell]} & 1 & 2 & 3 & 2 \\ \hline \end{array} \]

We can compute an optimal solution for a rod of length $3$ as follows:

Iteration $j$ ${s}[j]$ $x[1]$ $x[2]$ $x[3]$ $x[4]$ $j \leftarrow j-{s}[j]$

$-$ $-$ $-$ 0 0 0 0 $j=3$

$1$ $3$ $3$ 0 0 1 0 $j=3-3=0$

An optimal solution is the vector:

\[ (0,0,1,0) \]

We can compute an optimal solution for a rod of length $2$ as follows:

Iteration $j$ ${s}[j]$ $x[1]$ $x[2]$ $x[3]$ $x[4]$ $j \leftarrow j-{s}[j]$

$-$ $-$ $-$ 0 0 0 0 $j=2$

$1$ $2$ $2$ 0 1 0 0 $j=2-2=0$

An optimal solution is the vector:

\[ (0,1,0,0) \]

28.2.1 Number of steps¶

Let $S(n)$ denote the number of steps executed by DP1 in the worst case, where $n$ is the rod length. We compute $S(n)$ by counting how many times Line 2–Line 13 are executed.
In the worst case, the condition at line 7 is true at every iteration of the inner loop, and therefore line 8 is executed as often as line 7. The number of executions of the relevant lines is:
- Line 2 is executed $1$ time.
- Line 3 is executed $1$ time.
- Line 4 is executed $n$ times.
- Line 5 is executed $n$ times.
- Line 6 is executed $\displaystyle\sum_{\ell=1}^{n}\ell$ times.
- Line 7 is executed $\displaystyle\sum_{\ell=1}^{n}\ell$ times.
- Line 8 is executed $\displaystyle\sum_{\ell=1}^{n}\ell$ times.
- Line 11 is executed $n$ times.
- Line 13 is executed $1$ time.
Therefore, the total number of steps in the worst case is

\[ 1+1+n+n+\sum_{\ell=1}^{n}\ell+\sum_{\ell=1}^{n}\ell+\sum_{\ell=1}^{n}\ell+n+1 = 3+3n+3\sum_{\ell=1}^{n}\ell. \]

Using $\sum_{\ell=1}^{n}\ell=\dfrac{n(n+1)}{2}$, we obtain

\[ S(n)=3+3n+3\cdot\frac{n(n+1)}{2} = \frac{3n^2+9n+6}{2}. \]

Hence,

\[ S(n)=\Theta(n^2). \]

Indeed,

\[ \lim_{n\to\infty} \frac{\frac{3n^2+9n+6}{2}}{n^2} = \lim_{n\to\infty} \frac{1}{2}\left(3+\frac{9}{n}+\frac{6}{n^2}\right) = \frac{3}{2}\in\mathbb{R}_{>0}. \]

The DP algorithm executes

\[ S(n)=\Theta(n^2) \]

steps in the worst case.

Next: 28.3 A second DP algorithm

\(\ell\)	\(j\)	\({v}[\ell]\)	\(\mathit{m}\)	Action
\(-\)	\(-\)	0	\(-\)	\({v}[0]\leftarrow 0\)
	\(-\)	\(-\)	0	\(\mathit{m}\leftarrow 0\)
1	1	\(-\)	1	\(p[1]{+}{v}[0]=1{+}0=1>0\): \(\mathit{m}\leftarrow 1\)
	\(-\)	1	1	\({v}[1]\leftarrow \mathit{m}=1\)
	\(-\)	\(-\)	0	\(\mathit{m}\leftarrow 0\)
2	1	\(-\)	2	\(p[1]{+}{v}[1]=1{+}1=2>0\): \(\mathit{m}\leftarrow 2\)
	2	\(-\)	5	\(p[2]{+}{v}[0]=5{+}0=5>2\): \(\mathit{m}\leftarrow 5\)
	\(-\)	5	5	\({v}[2]\leftarrow \mathit{m}=5\)
	\(-\)	\(-\)	0	\(\mathit{m}\leftarrow 0\)
3	1	\(-\)	6	\(p[1]{+}{v}[2]=1{+}5=6>0\): \(\mathit{m}\leftarrow 6\)
	2	\(-\)	6	\(p[2]{+}{v}[1]=5{+}1=6=\mathit{m}\): no update
	3	\(-\)	8	\(p[3]{+}{v}[0]=8{+}0=8>6\): \(\mathit{m}\leftarrow 8\)
	\(-\)	8	8	\({v}[3]\leftarrow \mathit{m}=8\)
	\(-\)	\(-\)	0	\(\mathit{m}\leftarrow 0\)
4	1	\(-\)	9	\(p[1]{+}{v}[3]=1{+}8=9>0\): \(\mathit{m}\leftarrow 9\)
	2	\(-\)	10	\(p[2]{+}{v}[2]=5{+}5=10>9\): \(\mathit{m}\leftarrow 10\)
	3	\(-\)	10	\(p[3]{+}{v}[1]=8{+}1=9<10\): no update
	4	\(-\)	10	\(p[4]{+}{v}[0]=9{+}0=9<10\): no update
	\(-\)	10	10	\({v}[4]\leftarrow \mathit{m}=10\)

\(\ell\)	\(j\)	\({s}[\ell]\)	\(\mathit{m}\)	\(\mathit{t}\)	Action
\(-\)	\(-\)	\(-\)	\(-\)	\(-\)	Initial state
	\(-\)	\(-\)	0	0	\(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\)
1	1	\(-\)	1	1	\(1{+}0=1>0\): \(\mathit{m}\leftarrow 1\), \(\mathit{t}\leftarrow 1\)
	\(-\)	1	1	1	\({v}[1]\leftarrow \mathit{m}=1\), \({s}[1]\leftarrow \mathit{t}=1\)
	\(-\)	\(-\)	0	0	\(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\)
2	1	\(-\)	2	1	\(1{+}1=2>0\): \(\mathit{m}\leftarrow 2\), \(\mathit{t}\leftarrow 1\)
	2	\(-\)	5	2	\(5{+}0=5>2\): \(\mathit{m}\leftarrow 5\), \(\mathit{t}\leftarrow 2\)
	\(-\)	2	5	2	\({v}[2]\leftarrow \mathit{m}=5\), \({s}[2]\leftarrow \mathit{t}=2\)
	\(-\)	\(-\)	0	0	\(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\)
3	1	\(-\)	6	1	\(1{+}5=6>0\): \(\mathit{m}\leftarrow 6\), \(\mathit{t}\leftarrow 1\)
	2	\(-\)	6	1	\(5{+}1=6=\mathit{m}\): no update
	3	\(-\)	8	3	\(8{+}0=8>6\): \(\mathit{m}\leftarrow 8\), \(\mathit{t}\leftarrow 3\)
	\(-\)	3	8	3	\({v}[3]\leftarrow \mathit{m}=8\), \({s}[3]\leftarrow \mathit{t}=3\)
	\(-\)	\(-\)	0	0	\(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\)
4	1	\(-\)	9	1	\(1{+}8=9>0\): \(\mathit{m}\leftarrow 9\), \(\mathit{t}\leftarrow 1\)
	2	\(-\)	10	2	\(5{+}5=10>9\): \(\mathit{m}\leftarrow 10\), \(\mathit{t}\leftarrow 2\)
	3	\(-\)	10	2	\(8{+}1=9<10\): no update
	4	\(-\)	10	2	\(9{+}0=9<10\): no update
	\(-\)	2	10	2	\({v}[4]\leftarrow \mathit{m}=10\), \({s}[4]\leftarrow \mathit{t}=2\)

Iteration	\(j\)	\({s}[j]\)	\(x[2]\)	\(j \leftarrow j-{s}[j]\)
\(-\)	\(-\)	\(-\)	0	\(j=4\)
\(1\)	\(4\)	\(2\)	1	\(j=4-2=2\)
\(2\)	\(2\)	\(2\)	2	\(j=2-2=0\)

Iteration	\(j\)	\({s}[j]\)	\(x[1]\)	\(x[2]\)	\(x[3]\)	\(x[4]\)	\(j \leftarrow j-{s}[j]\)
\(-\)	\(-\)	\(-\)	0	0	0	0	\(j=3\)
\(1\)	\(3\)	\(3\)	0	0	1	0	\(j=3-3=0\)

Iteration	\(j\)	\({s}[j]\)	\(x[1]\)	\(x[2]\)	\(x[3]\)	\(x[4]\)	\(j \leftarrow j-{s}[j]\)
\(-\)	\(-\)	\(-\)	0	0	0	0	\(j=2\)
\(1\)	\(2\)	\(2\)	0	1	0	0	\(j=2-2=0\)