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 ${\displaystyle 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 ${\displaystyle s}$. We set ${\displaystyle C}$ equal to the maximum value of ${\displaystyle s}$.

Step 3: Specify the allowable actions for each state in each stage
This can be defined as:
${\displaystyle 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 ${\displaystyle s}$, and each stage, or ${\displaystyle n}$. This can also be called ${\displaystyle 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 ${\displaystyle f_{n+1}^{*}(s)=0}$ for all values of ${\displaystyle s}$. Here, we can note that ${\displaystyle s=0,...,C}$

Step 6: Define the recurrence relation
During this step, we make an allowable decision involving ${\displaystyle j}$ items for the remaining capacity ${\displaystyle s}$ for items ${\displaystyle n}$. We can write this statement as:
${\displaystyle 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 ${\displaystyle s}$, ${\displaystyle f_{n}^{*}(s)}$, and optimal values for all ${\displaystyle n}$ variables. This step can be done manually or by using programming.

Step 8: Arrive at the optimal solution
Once the value for ${\displaystyle 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 ${\displaystyle n}$, calculate our remaining space ${\displaystyle s}$, and use that value to arrive at an optimal value for all ${\displaystyle 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:

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

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

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

Unused Capacity s ${\displaystyle f_{1}^{*}(s)}$ Type 1 opt ${\displaystyle U_{1}^{*}(s)}$ ${\displaystyle f_{2}^{*}(s)}$ Type 2 opt ${\displaystyle U_{2}^{*}(s)}$ ${\displaystyle 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