# Difference between revisions of "Eight step procedures"

Line 11: | Line 11: | ||

'''Step 1: Specify the stages of the problem''' <br /> | '''Step 1: Specify the stages of the problem''' <br /> | ||

• The stages of a dynamic programming problem can be defined as points where decisions are made. These are often denoted with the variable n. <br /> | • The stages of a dynamic programming problem can be defined as points where decisions are made. These are often denoted with the variable n. <br /> | ||

− | Step 2: Specify the states for each stage <br /> | + | <br /> |

+ | '''Step 2: Specify the states for each stage''' <br /> | ||

• 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. <br /> | • 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. <br /> | ||

− | Step 3: Specify the allowable actions for each state in each stage <br /> | + | <br /> |

+ | '''Step 3: Specify the allowable actions for each state in each stage''' <br /> | ||

• This can be defined as: <br /> | • This can be defined as: <br /> | ||

o Un(s) or j = 0,1,…,min{a[n], floor(s/w[n])} <br /> | o Un(s) or j = 0,1,…,min{a[n], floor(s/w[n])} <br /> | ||

− | Step 4: Describe the optimization function using an English-language description. <br /> | + | <br /> |

+ | '''Step 4: Describe the optimization function using an English-language description.''' <br /> | ||

• 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) <br /> | • 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) <br /> | ||

− | Step 5: Define the boundary conditions <br /> | + | <br /> |

+ | '''Step 5: Define the boundary conditions''' <br /> | ||

• 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 <br /> | • 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 <br /> | ||

− | Step 6: Define the recurrence relation <br /> | + | <br /> |

+ | '''Step 6: Define the recurrence relation''' <br /> | ||

• 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: <br /> | • 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: <br /> | ||

o f*n(s) = max j=0,1,…,min{a[n], floor(s/w[n]0} {b[n,j]+f*n+a(s-j*w[n])} <br /> | o f*n(s) = max j=0,1,…,min{a[n], floor(s/w[n]0} {b[n,j]+f*n+a(s-j*w[n])} <br /> | ||

− | Step 7: Compute the optimal value from the bottom-up <br /> | + | <br /> |

+ | '''Step 7: Compute the optimal value from the bottom-up''' <br /> | ||

• In this step, a table is made <br /> | • In this step, a table is made <br /> | ||

## Revision as of 17:35, 20 November 2020

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 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 Un(s) or j = 0,1,…,min{a[n], floor(s/w[n])}

**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) = max j=0,1,…,min{a[n], floor(s/w[n]0} {b[n,j]+f*n+a(s-j*w[n])}

**Step 7: Compute the optimal value from the bottom-up**

• In this step, a table is made