Eight step procedures
Author: Eljona Pushaj, Diana Bogdanowich, Stephanie Keomany
Steward: Fengqi You
Introduction
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 .
Step 2: Specify the states for each stage
• The states of a problem are defined as the knowledge necessary to make a decision, or . We set equal to the maximum value of .
Step 3: Specify the allowable actions for each state in each stage
• This can be defined as:
o
Step 4: Describe the optimization function using an English-language description.
• In this sentence, we describe the optimization function for each state, or , and each stage, or . This can also be called
Step 5: Define the boundary conditions
• This helps create a starting point to finding a solution to the problem. First, we set for all values of . Here, we can note that
Step 6: Define the recurrence relation
• During this step, we make an allowable decision involving items for the remaining capacity for items . We can write this statement as:
o
Step 7: Compute the optimal value from the bottom-up
• In this step, a table is made