Eight step procedures

Author: Eljona Pushaj, Diana Bogdanowich, Stephanie Keomany
Steward: Fengqi You

Theory, Methodology, and/or Algorithmic Discussion

Methodology

To solve a problem using the 8-step procedure, one must use the following steps:

Step 1: Specify the stages of the problem
The stages of a dynamic programming problem can be defined as points where decisions are made. These are often denoted with the variable $n$.

Step 2: Specify the states for each stage
The states of a problem are defined as the knowledge necessary to make a decision, or $s$. We set $C$ equal to the maximum value of $s$.

Step 3: Specify the allowable actions for each state in each stage
This can be defined as:
$U_{n}(s)\,or\,j\,=\,0,1,...,min\left\{a[n],\left\lfloor {\frac {s}{w[n]}}\right\rfloor \right\}$

Step 4: Describe the optimization function using an English-language description.
In this sentence, we describe the optimization function for each state, or $s$, and each stage, or $n$. This can also be called $f_{n}^{*}(s)$

Step 5: Define the boundary conditions
This helps create a starting point to finding a solution to the problem. First, we set $f_{n+1}^{*}(s)=0$ for all values of $s$. Here, we can note that $s=0,...,C$

Step 6: Define the recurrence relation
During this step, we make an allowable decision involving $j$ items for the remaining capacity $s$ for items $n$. We can write this statement as:
$f_{n}^{*}(s)={\overset {max}{j=0,1,...,min\left\{a[n],\left\lfloor {\frac {s}{w[n]}}\right\rfloor \right\}}}\left\{b[n,j]+f_{n+1}^{*}(s-j*w[n])\right\}$

Step 7: Compute the optimal value from the bottom-up
In this step, a table is made containing all $s$, $f_{n}^{*}(s)$, and optimal values for all $n$ variables. This step can be done manually or by using programming.

Step 8: Arrive at the optimal solution
Once the value for $f_{n}^{*}(s)$ is computed, we would look at the optimal decision that corresponds to the table entry for that value. We start with the optimal value for our first $n$, calculate our remaining space $s$, and use that value to arrive at an optimal value for all $n$.

Numerical Example

Weight capacity of C=5 and N=2

Item types are stages: n=1,2

Remaining capacity s= 1,2,3,4,5

Boundary Conditions:

$f_{n+1}^{*}(s)=0$, s=0,1,2,3,4,5 C=5

$U_{2}(5)\,=\,0,1,...,min\left\{a[2],\left\lfloor {\frac {5}{w[2]}}\right\rfloor \right\}$= {0,1,2}

$f_{2}^{*}(5)=max\left\{b[2,j]+f_{3}^{*}(5-j*w[2])\right\}$=

Unused Capacity s	$f_{1}^{*}(s)$	Type 1 opt $U_{1}^{*}(s)$	$f_{2}^{*}(s)$	Type 2 opt $U_{2}^{*}(s)$	$f_{3}^{*}(s)$
5	9	0	9	2	0
4	9	0	9	2	0
3	4	0	4	1	0
2	4	0	4	1	0
1	0	0	0	0	0
0	0	0	0	0	0