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 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 $.