Dynamic Programming Tutorial
Author 
Message 
Saad

Posted: Thu Jan 03, 2008 11:26 pm Post subject: Dynamic Programming Tutorial 


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
Description: 

Download 
Filename: 
Dynamic Programming Tutorial By Saad Ahmad.pdf 
Filesize: 
38.69 KB 
Downloaded: 
11808 Time(s) 






Sponsor Sponsor



HeavenAgain

Posted: Thu Jan 03, 2008 11:31 pm Post subject: RE:Dynamic Programming Tutorial 


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

Posted: Fri Jan 04, 2008 9:47 pm Post subject: RE:Dynamic Programming Tutorial 


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

Posted: Fri Jan 04, 2008 9:58 pm Post subject: RE:Dynamic Programming Tutorial 


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

Posted: Fri Jan 04, 2008 11:06 pm Post subject: Re: Dynamic Programming Tutorial 


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

Posted: Fri Jan 04, 2008 11:39 pm Post subject: RE:Dynamic Programming Tutorial 


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

Posted: Sat Jan 05, 2008 12:38 am Post subject: RE:Dynamic Programming Tutorial 


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






Tony

Posted: Sat Jan 05, 2008 2:29 am Post subject: Re: RE:Dynamic Programming Tutorial 


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)

Tony's programming blog. DWITE  a programming contest. 




Sponsor Sponsor



Clayton

Posted: Sat Jan 05, 2008 10:43 am Post subject: RE:Dynamic Programming Tutorial 


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

Posted: Sat Jan 05, 2008 12:40 pm Post subject: RE:Dynamic Programming Tutorial 


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^(N1). (Actually, if I can be really picky, it would approach 3^(N1) 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

Posted: Sat Jan 05, 2008 2:54 pm Post subject: Re: Dynamic Programming Tutorial 


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

Posted: Sat Jan 05, 2008 8:33 pm Post subject: RE:Dynamic Programming Tutorial 


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.

Tony's programming blog. DWITE  a programming contest. 




liza22

Posted: Wed Jan 16, 2019 2:36 am Post subject: Re: Dynamic Programming Tutorial 


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.







