Eight step procedures

Author: Eljona Pushaj, Diana Bogdanowich, Stephanie Keomany
Steward: Fengqi You

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 $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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} . This can also be called Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}_{n+1}(s) = 0} for all values of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} . Here, we can note that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s=0,...,C }

Step 6: Define the recurrence relation
• During this step, we make an allowable decision involving Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} items for the remaining capacity Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} for items Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} . We can write this statement as:
o Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}_{n}(s)} , and optimal values for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} variables. This step can be done manually or by using programming.

Step 8: Arrive at the optimal solution
• Once the value for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , calculate our remaining space Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} , and use that value to arrive at an optimal value for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .