-
August 23rd, 2011, 02:57 PM
#1
Dynamic Programming - Rod Cutting
Hey folks,
I was looking at the CLRS the other day just to refresh my mind a little bit and bumped into the classic rod cutting problem.
The classic bottom-up solution for this is the following:
1: let r[0..n] be a new array
2: r[0] = 0
3: for j = 1 to n
4: q = -1
5: for i = 1 to j
6: q = max(q, p[i] + r[j-i])
7: r[j] = q
8: return r[n]
Now there is something I keep thinking about. Why do we keep reusing p[i] on L.6? I mean let's say we have j = 4 then it would compute the following combinations:
1 + 3
2 + 2
3 + 1
4 + 0
what's the point of computing "3 + 1" twice really. What I am suggesting is we stop using p[] and only use r[] and stop at floor(j/2).
1: let r[0..n] be a new array
2: r[0] = 0
3: for j = 1 to n
4: q = p[j]
5: for i = 1 to floor(j/2)
6: q = max(q, r[i] + r[j-i])
7: r[j] = q
8: return r[n]
Does anyone see something wrong with this approach?
Thanks,
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|