Eight step procedures

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

Theory, Methodology, and/or Algorithmic Discussion

Definition

To solve a problem using the 8-step procedure, one must follow 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:
o $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:
o $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$.