Problems understanding dynamic programming

[Tomislav Novak]

Hello!

I've read the chapter about dynamic programming in Introduction to Algorithms and I understand it in theory, but in practice I have difficulties with the optimal sub-structure property - there are many problems where I find it difficult to determine which subproblems ensue by making a choice and how to solve this problems optimally.

For example, consider the standard knapsack problem - N elements with different sizes and values, and a M-sized knapsack. When choosing an element k to put into the bag, one is left with a knapsack of size M - size[k]. Now this has to be solved optimally...

However, I don't know how to determine the structure of the optimal solution when there're some constrains. For example, there is a limited number of each element (eg. 6 elements of one kind, 3 elements of another kind...), or the problem is to find a maximum possible value, but if there're more ways to get this optimal value, one must print the one that includes the smallest number of elements...

I hope that you could understand from this post what causes me trouble and give me some advice and/or good web sites or books where I can read more on the subject.

Thanks.

[Andrew Neitsch]

The way I do dynamic programming is to write a nice recursive function, and if it is slow, store the computed results in an array.

In the case of a recursive function, it's not hard to satisfy the constraints. E.g. with the knapsack problem, to find the solution that includes the smallest number of elements, my function would return the number of elements as well as the optimal cost; then for each state I could reach from the current state, I would test for the minimal element first on the value (plus the cost of getting there, if necessary), then if there is a tie, test for the minimal number of elements selected.

Which "Introduction of Algorithms" is it? The best algorithms book I've encountered is Sedgewick's "Algorithms in C", though it's light on dynamic programming and doesn't cover what you are asking about.

[chengl]

I am also facing the same problem. It is difficult to formulate the solutions with DP sometimes. I read some examples in introduction to algorithms , it seems I had mastered the idea of DP, actually find out not when trying to solve other problems myself. Normally it is said as that book "beneath every greedy algorithm, there is almost always a more cumbersome dynamic programming solution". I am trying to solve some problems that require Greedy with DP. Generally, problems like "ways to change coin", it seems they are following the idea that
Let C[i, j] be the number of ways to change amount j money with the first i kinds of demontions, then construct the solution by using the first i-1 kinds of demontions only plus changing the amount(original amount is deducted by the i st kind demonitions) with the first i kinds of demontions. This is what is called optimal solutions within the solution to subproblem.
I could understand the optimal substructure of the problem. When I try to solve the minimal cover problem, I have no idea of how to formulate the sentence like "Let....". The minimal set problem:
given a set of numbers {x1, x2...xn}, and a set of interval [al, ar] [bl, br].... find the minimal set of intervals that cover these numbers.
Assume the soluation is known, then remove any interval in the solution and its covered numbers are still optimal solution to its subproblems. But how to formulate or how to construct its recursive solution in this way at the first step of DP? Any help are highly appreciated.

[Andrew Neitsch]

I have not done the minimal set problem, and have only thought about it for two minutes, but here is how I would do it

Have a function
best(next number to consider,chosen set of intervals)
= minimum over all intervals I that cover the next number to consider, of best(next number to consider+1,chosen set of intervals joined with I).

Your answer is then best(0,no intervals chosen).

If this is an online judge problem, I could try it.

[chengl]

I have not done the minimal set problem, and have only thought about it for two minutes, but here is how I would do it

Have a function
best(next number to consider,chosen set of intervals)
= minimum over all intervals I that cover the next number to consider, of best(next number to consider+1,chosen set of intervals joined with I).

Your answer is then best(0,no intervals chosen).

If this is an online judge problem, I could try it.

I don't understand, can you please explain a little bit? For example, you can try the numbers {3, 1, 5, 2}, and the set of intervals [2, 3] [3, 4] [0, 2] and [2, 6], the solution should be [0, 2] [2, 6].

[Andrew Neitsch]

You have a function best(int n,set of intervals). If the given set of intervals covers the 0th through n-1th numbers, then best(n,set of intervals) is the minimum, over all intervals (call each one I in turn) containing the nth number, of best(n+1,set of intervals \[Union] I).

best(int n,set of intervals) is the fewest number of intervals needed to cover the 0th through nth numbers, having covered the 0th through nth numbers with the given set of intervals.

[chengl]

You have a function best(int n,set of intervals). If the given set of intervals covers the 0th through n-1th numbers, then best(n,set of intervals) is the minimum, over all intervals (call each one I in turn) containing the nth number, of best(n+1,set of intervals \[Union] I).

best(int n,set of intervals) is the fewest number of intervals needed to cover the 0th through nth numbers, having covered the 0th through nth numbers with the given set of intervals.

Hm..thank you so much! I also thought a way to solve it. Sort the x1, x2...xn
and sort the interval by the left end(al, bl, cl....) with increasing order..then we can establish a table, with entry
Sij = 1 if it the interval i contains the xj.
Of course only fill it when necessary.so determine the minimal interval according to this table.