Dynamic Programming

Example 1: Dynamic Programming Example

The general idea behind dynamic programming is to find the optimal solution to a small part of the whole problem. Using the
previous solution, enlarge the problem slightly and find the new optimum solution. Continue enlarging until you have solved the
whole problem, then trace back to find the solution.

The characteristics of a problem that can be solved using dynamic programming are the following:

problem can be divided into stages
each stage has one or more states
you make a decision at each stage
the decision you make affects the state for the next stage
there is a recursive relationship between the value of the decision at the stage and the previously found optima

Example: The number of students that fail ENG101 depend on the number of TAs assigned to each section. There are six TA available
to be assigned to the course and there are four sections. How many TAs should be assigned to each section of the course to have
the least students fail?

The first step is to formulate the solution:

stages: ENG101 sections (ie. 1st: section D, 2nd: section C and D, 3rd: section B, C and D, 4th: section A, B, C and D)
state at a stage: number of TAs available to be assigned
decision: how many TAs to assign to section i
descision update to state: number of available TAs to assign is reduced according to the decision.
recursive value relationship:

Press the Start button to begin the example.

This animation was made using Alligator Flash Designer 7. More information about this program is available at Selteco Alligator.
You can view the source code for this animation using the trial verson of Alligator Flash Designer 7 and