
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 bottomup 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[ji])
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[ji])
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
This is a CodeGuru survey question.
Featured
