Eight step procedures: Difference between revisions
Line 17: | Line 17: | ||
'''Step 3: Specify the allowable actions for each state in each stage''' <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 | o <img src="https://latex.codecogs.com/gif.latex?U_{n}(s)\,&space;or\,&space;j\,&space;=\,&space;0,1,...,min\left&space;\{&space;a[n],&space;\left&space;\lfloor&space;\frac{s}{w[n]]}&space;\right&space;\rfloor&space;\right&space;\}" title="U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]]} \right \rfloor \right \}" /> <br /> | ||
<br /> | <br /> | ||
'''Step 4: Describe the optimization function using an English-language description.''' <br /> | '''Step 4: Describe the optimization function using an English-language description.''' <br /> |
Revision as of 17:43, 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 <img src="https://latex.codecogs.com/gif.latex?U_{n}(s)\,&space;or\,&space;j\,&space;=\,&space;0,1,...,min\left&space;\{&space;a[n],&space;\left&space;\lfloor&space;\frac{s}{w[n]]}&space;\right&space;\rfloor&space;\right&space;\}" title="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) = 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