Dynamic Programming is one very useful technique for solving problems like the Knapsack problem.
The basic idea of Dynamic programming is to break down a problem in recursive subproblems. Each subproblem must be easy to solve, and its solution stored in some data structure to be used again.
In a schematic drawing, it’s something like this:
Dynamic programming is not a general procedure to be applied in any problem. The problem has to allow it. Richard Bellman, the creator of Dynamic Programming, called it “Principle of optimallity”. It is like saying “this method works in the problems it works, and doesn’t works in the problems it doesn’t works”. But mathematicians love this kind of concept, because they can ask: which problems has the principle of optimality? Is the Knapsack one of them?
Since this method is not general, the programmer has to design a new method for every different problem and also figure out if the problem has the principle of optimality.
But, despite all these observations, it is a useful way of thinking.
1) It is easy to compute the solution with 1 item for a range of weights.
Array of values
Array of picked itens:
2) We increase the number of itens, and compare current solution versus solution with new item.
Complete array with 2 items.
Proceeding this way, we get the full evaluation matrix.
The optimum is to pick itens 1, 3 and 4, and the value of those items is 14,000.
Note that, in order to get the optimum, I had to calculate every solution for 1 to number of itens and 1 to number weigths. Thus, the computational effort to calculate it is proportional to N*maxW.
The problem happens when N and W are large. It needs a lot of computation processing.
Knapsack is a pseudo polynomial time algorithm. Polynomial because it is proportional to N. But pseudo since it is not quite true it is proportional to N – it is also proportional to W, and W can be very very large. One day I’ll post a more detailed way of thinking of this.
Divide and conquer
Other question I had when studying dynamic programming for the first time was: what is the difference of this method compared to divide and conquer methods?
I think this discussion deserves a post apart, but just to give a simple explanation, divide and conquer has a “horizontal” structure, with subproblems independent of each other, while dynamic programming has a “nested” structure, with subproblems dependent of other subproblems.
It uses the Random case generator of previous post and generates a solution for this case.
Dynamic programming can be applied in several other cases. Cutting stock problems are also a classic application.
One less known application is in the optimization of forest multiproducts. We have a forest of eucalyptus. Each tree has to be cut in several pieces. Each piece has a different diameter (since the tree is larger in the base). A product is a combination of diameter and lenght. Given a demand, how can I minimize the waste and maximize the use of the forest?
In the next posts, I’ll show alternative methods for solving the Knapsack Problem.