Dynamic Programming Tutorial

[Saad]

I decided I would write this tutorial at the start of the week on Dynamic Programming and it's finished. I've attached the tutorial in pdf format for better formating.

Enjoy
Saad

[HeavenAgain]

oh nice man! really nice, altho i havnt read it yet, i know this is gonna be good
DP is a long topic and could be a handful of questions, hope you are ready!!

[Saad]

Yes it is a long topic, and i'm ready to answer questions. I am working on adding more examples when i get more time.

[HeavenAgain]

wanna explain knapsack problem?
consider there is no value ($) of items, just their weight
i used bitmask to solve these problems, but you know.... DP totally owns

[Saad]

I'll talk about how to solve it with items of value

First step of Dynamic Programming is to define the optimal structure for the solution. Let W represent the maximum weight which we can carry. Let N represent amount of items.
For the optimal structure we can say that if we take out weight[i] from our optimal options, then W - weight[i] must be an optimal solution. Why?, this is because if is a better way to use W - weight[i] then we can substitute our current way with the optimal path.

The second step is to create a recursive solution.

From our optimal structure we create a function MaxAmount(i, W) which returns the maximum value of items that can be picked up:

code:

/   max (MaxAmount(i - 1, W), MaxAmount (i -1, W - weight[i] + value[i])   If i > 0, and W - weight[i] >= 0 MaxAmount (i, W) = |   MaxAmount (i -1, W)            If i > 0, and W - weight[i] < 0                     \    0                                       If i = 0

Step three is to solve it in a bottom up fashion
Let max_amount a 2D array of dimensions NxW

code:

for i : 1 to N    // We have no more room we can add no more items     max_amount[i, 0] = 0 end for w : 1 to W  // We have no more items to add     max_amount[0, w] = 0 end for i : 1 to N     for w : 1 to W         if weight[i] <= w then             max_amount[i, w] = max (max_amount[i - 1, w], max_amount[i - 1, w - weight[i]] + value[i])  // Best choice out of including or not including the current item         else             max_amount[i,w] = max_amount[i -1, w] // We don't have room for an item         end     end end print (max_amount[N,W])   // Get the maximum amount at [N,W] which is our optimal solution

The comments should sum up how I converted the recursive algorithm to a bottom up way.

Edit: Fixed some minor errors. PS can a mod correct my sentence in my first post i meant to say
I've attached the tutorial in pdf format for better formating.
Rather then
I've attached the tutorial pdf for for better formating.

[HeavenAgain]

i will have to try this out, when i have a clearer mind.
what this is doing is something like... for example with the case, 8 is limit and we have 1, 4, 5, 3
1, 4, 3
4, 1, 3
5, 3
3, 1, 4
which lists all the possible combination?

and ps, in your code there, W is the number of weights? not the weight limit? if it is the weight limit, why would you do the "for w : 1 to W" loop?

thanks

[CodeMonkey2000]

Wow this is really useful. These types of problems are fairly frequent in contests.

[Tony]

we had the knapsack problem on the last DWITE

HeavenAgain @ Fri Jan 04, 2008 11:39 pm wrote:

if it is the weight limit, why would you do the "for w : 1 to W" loop?

To be sure in our solution, we need to check all valid possible combinations (otherwise we might have missed something). The major ideas behind dynamic programming though, is that a) if the current partial trial is worse than the best solution so far, we discard it, and b) keep track of the previous calculations, so that we don't repeat the same computations. We are effectively trading space for computation power (this is how rainbow tables work).

A good example of dynamic programming involves working with factorials, or fibonacci, or such recursively defined values. For example: 5! + 4! = ?

5! = 5*4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1

PLUS
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1

Except that since we already calculated the value of 4! while we were calculating 5!, we just look that up, and save ourselves 4 computation calls. If we store the results in an array, the lookup time is O(1)

[Clayton]

Tony wrote:

PLUS
4! = 3*2!
2! = 2*1!
1! = 1*0!
0! = 1

Just a small correction:

PLUS
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1

[PaulButler]

Great stuff. + bits!

I noticed one little thing, you said for the first problem there are 3^N possibilities, but if I understand the question properly it would be 3^(N-1). (Actually, if I can be really picky, it would approach 3^(N-1) as N -> infinity, since when you are on either edge of the grid you would only have two choices instead of 3). Or did I misunderstand the problem?

[Saad]

3^N was an approximation, Calculating the number of possibilities although is rather simple.

code:

Amount (n) =  / 1    if r = N               | 0    if c = 0 or c > N                \  Amount(r + 1, c - 1) + Amount ( r + 1, c) + Amount ( r + 1, c + 1)   Otherwise

[Tony]

Clayton - thx for the correction.

Paul - as N approaches infinity, we really would only care that this is O(c^n) ... which is absolutely horrible.

[liza22]

Hi,

Thanks for sharing this pdf with us. I will definitely be going to read it. Dynamic programming is a very specific topic in programming competitions. No matter how many problems have you solved using DP, it can still surprise you. Hope after reading this pdf, it will help me to solve my few problems that I have found in programming.