Computer Science Canada

Dynamic Programming Tutorial
Author:  Saad [ 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 Very Happy
Saad
Author:  HeavenAgain [ 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 Very HappyVery Happy
DP is a long topic and could be a handful of questions, hope you are ready!!
Author:  Saad [ 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.
Author:  HeavenAgain [ Fri Jan 04, 2008 9:58 pm ]
Post subject:  RE:Dynamic Programming Tutorial
Very Happy 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 Crying or Very sad
Author:  Saad [ 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.
Author:  HeavenAgain [ 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?

Smile thanks
Author:  CodeMonkey2000 [ 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.
Author:  Tony [ Sat Jan 05, 2008 2:29 am ]
Post subject:  Re: RE:Dynamic Programming Tutorial
we had the knapsack problem on the last DWITE Wink

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)
Author:  Clayton [ 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
Author:  PaulButler [ Sat Jan 05, 2008 12:40 pm ]
Post subject:  RE:Dynamic Programming Tutorial
Great stuff. + bits! Smile

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?
Author:  Saad [ 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


Author:  Tony [ 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.
Author:  liza22 [ 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.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy