-----------------------------------

Saad

Thu Jan 03, 2008 11:26 pm


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 :D  
Saad


-----------------------------------

HeavenAgain

Thu Jan 03, 2008 11:31 pm


RE:Dynamic Programming Tutorial

-----------------------------------

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


-----------------------------------

Saad

Fri Jan 04, 2008 9:47 pm


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

Fri Jan 04, 2008 9:58 pm


RE:Dynamic Programming Tutorial

-----------------------------------

:D 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 :cry:


-----------------------------------

Saad

Fri Jan 04, 2008 11:06 pm


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                    /   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

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]  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

Sat Jan 05, 2008 2:54 pm


Re: Dynamic Programming Tutorial

-----------------------------------

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

 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

Sat Jan 05, 2008 8:33 pm


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.


-----------------------------------

liza22

Wed Jan 16, 2019 2:36 am


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.