 Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki Blog Search Turing Chat Room Members
Dynamic Programming Tutorial       Author Message  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 Description: Filesize:  38.69 KB    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!!   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    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.    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^(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?   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. Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First        Page 1 of 1  [ 13 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: