In computer science Dynamic Programming is a powerful algorithmic paradigm that can help solve seemingly intractable problems in viable ways.
The rather confusing name ‘Dynamic Programming’ originates from quite an amusing story.
First of all the word ‘Programming’ comes from a time when programmers weren’t programming computers, but were rather planners for logistic purposes (and such).
It is said that Richard Bellman invented the term as some sort of euphemism to avoid pissing off his military boss who hated the word ‘research’ and would turn violent if anyone used it in his presence. So to hide the mathematical character of his work he needed a term that wouldn’t get him into trouble for working on the planning of optimal multi-stage processes, so ‘Dynamic Programming’ it was.
In many algorithmic problems it is common to split a problem down into smaller sub-problems, solve each sub-problem and then re-combine solutions to a full solution for the original problem. The paradigm I just described is commonly referred to as Divide-and-Conquer. The methods to achieve this can vary, but very often some naive form of recursion can be thought out with relative ease. Unfortunately such solutions may lead to an exponential explosion of sub-problems if you allow the recursion to branch.
Certain problems however have the property that generated sub-problems begin to repeat themselves in an overlapping manner. This means the recursive solution does a lot of unnecessary work since it would be possible to avoid re-solving the same problem over and over again if the solution was saved the first time it was encountered and subsequently looked up in a table.
Dynamic Programming algorithms exploit this overlapping property in the way described above to create more efficient solutions.
For these reasons Dynamic Programming solutions can often bring down the runtime of a naive exponential time algorithm to polynomial time. For all practical purposes this can mean the difference between usable and not usable.
A basic example is that of computing the term of the Fibonacci sequence.
One of the hallmark applications of Dynamic Programming is in solving optimization problems.
The problem should, apart from having overlapping sub-problems also be re-combinable. That is to say, optimal solutions to smaller problems make up optimal solutions to bigger problems. An optimization problem with this property is said to exhibit optimal substructure. These two properties together are pre-requisites for Dynamic Programming solutions.
In the remainder of this post we will look at various other instances of Dynamic Programming problems.
Now let’s look at a slightly trickier problem.
The time management problem where tasks are given taking hours to complete and have value for is also equivalent to the Binary Knapsack problem. The knapsack capacity is given by a global deadline and the problem is to pick out the tasks that will maximize value before hitting deadline. In general any problem which fits the integer program specification can be solved using the same algorithm.
The final problem along with its many variations is a very intriguing problem which occurs naturally in many real-world situations. Unfortunately its general formulation is very hard to solve (NP-hard in fact).
However if we make some simplifying assumptions it can be solved optimally in polynomial time using a Dynamic Programming approach (though still very unpractical for larger inputs).
The bin packing problem arises naturally in many logistics problems such as the problem of finding the minimum number of lorries required to deliver goods of different sizes or the minimum number of shelves needed in a storage room. It also arises in advertisement problems, where you for instance want to fit a certain number of commercials of different length in a minimum series of 3 minute television breaks. As we have seen above it can also arise in scheduling problems. Wikipedia mentions another interesting variant of the Bin Packing problem where items could occupy less space in comparison to the sum of their individual sizes when packed together. This arises in the problem of minimizing physical servers hosting virtual machines (VMs), where resource sharing may occur on the host. For that reason this variation of the problem is referred to as VM packing.
Needless to say the Bin Packing problem is very important.
Many other nice variations of this problem also exists. For example one may be interested in looking at bins of multiple capacities, higher dimensional extensions of the bins/items, different geometrical shapes of the bins/items or looking at online versions of these problems (i.e where items arrive incrementally) and etc…
We saw that the Bin Packing problem admitted a polynomial time solution when restricted to distinct types of items. The performance however is still rather dreadful in practice. Often when dealing with difficult problems such as the Bin Packing problem one has to resort to heuristics and approximation algorithms.
One simple such heuristic is the Next-Fit packing algorithm which traverses the items once and checks whether the next item fits in the last bin. If it does, then it puts it there, if it doesn’t then it opens a new bin. This may seem like a rather crude way of going about it, but the algorithm has certain advantages.
For instance it is only linear time, works online and outputs at most twice the optimal number of bins [Exercise 1].
Yet another simple heuristic which is slightly slower [ or less depending on implementation] but gives better results is the First-Fit packing algorithm. This algorithm repeatedly traverses the list of items and inserts into the last bin the first item that fits into it. If no item fits, it opens a new bin and goes through the list again until all items are gone.
This concludes our discussion about dynamic programming.
There are many other interesting problems which fit this topic. You will see two of them in the exercises below, but I recommend signing up to places like TopCoder and check out their practice rooms for a large variety of other Dynamic Programming problems of varying difficulty.
If you are interested in algorithms in general you may also find it worthwhile to check out Wikipedia’s list of algorithms.
The standard book carried around by all computer scientists you can find here.