-
Website
http://20bits.com -
Original page
http://20bits.com/articles/introduction-to-dynamic-programming/ -
Subscribe
All Comments -
Community
-
Top Commenters
-
Felix Purnama
3 comments · 1 points
-
hadley
2 comments · 1 points
-
adamheroku
2 comments · 3 points
-
twiss
2 comments · 1 points
-
maxima128
2 comments · 1 points
-
-
Popular Threads
"... plays a roll..."
Looks good to mean. I get the maximum sum to be 3 and the range to be (0,2). The range it returns is meant to be applied in python, so that, e.g., (0,2) means [1,2,-4,1][0:2].
> means that we cannot include a[j:i+1] in our subarray since
> any such subarray will have a smaller sum than a subarray without it.
What if all the numbers in the array are negative? I guess this is okay if the Maximum Subarray can be zero length.
If the subarray can't be zero length, do we have to go to a O(N^2) solution? Would it suffice to keep track of the largest single number?
Great post. What wordpress plugin do you use to embed code in your posts?
Thanks
It's called Dean's Code Highlighter.
give some code implementation also...
http://fudge.fit.edu/Problems/Archive
specifically the phrase "if t+a[i] is negative set t = 0 and set the left-hand bound of the optimal subarray to i+1" should be revised, since actually the optimal subarray does not change; only the starting point of further consideration changes. (consider [1,2,-5,1,1,-2]: t goes negative but the optimal subarray remains at the front.)
But it seems I'm the first one to actually try your function A(..), as it doesn't work:
>>> A([10, 20], [30, 40], 2, 10000)
Traceback (most recent call last):
File "", line 1, in
File "", line 3, in A
IndexError: list index out of range
You're mixing zero-based arrays (Python) and one-based arrays (your text), so the correct function A would look like this:
def A(w, v, i,j):
if i == 0 or j == 0: return 0
if w[i-1] > j: return A(w, v, i-1, j)
else: return max(A(w,v, i-1, j), v[i-1] + A(w,v, i-1, j - w[i-1]))
Cheers
Horst
Perl also has a module called Memoize and its been part of the core Perl library for some years now.
Here's an article about Memoization by the author of the above module.
/I3az/
PS. Nice article.
I'm using a Ruby graphing library called Gruff.
Thanks. I wrote this like a year and a half ago — I'm surprised nobody has caught that yet.
Regarding the knapsack problem, once the table is ready, the complexity is indeed only O(nW)
But building the table itself is of exponential cost in terms of running time, correct?
We go through every single possibility using recursion to build the table, and I think running time to build the table is n^m. It would be great if you could clarify.
Second, your graphs are hard to read. Why does your graph use a gradient background? The change in contrast makes it difficult to read and gives really no benefit.
Also your graphs go against the norm, the label of the y axis is upside down. I don't care if it is your software or some designer jerk being a douchebag suggesting this is better...
IT ISN'T. I have to parse through 100s of chart a day in my day job and this kind of shit just pisses me off. I shouldn't have to fight with your eye-candy.
Sorry for making you work so hard. Do you have any examples of good graphs?
Help me learn — don't just berate me.
By the way, I believe your fib2 function is missing a line. It is incorrect for n=0. I think it should read:
def fib2(n):
if n == 0: return 0
n2, n1 = 0, 1
for i in range(n-2):
n2, n1 = n1, n1 + n2
return n2 + n1
Cheers
Simon
def fib2(n):
n2, n1 = 0, 1
for i in range(n):
n2, n1 = n1, n1 + n2
return n2