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