[LivingNightmare]

I'm having alot of trouble comming up with a dynamic programming solution to the following problem. We were initially required to solve problem a) first: Given a a set of strings, we had to format the text such that we maximized the number of lines. Each line had to have 72 - 80 characters. However, the line could have less than 72 characters if the following word did not fit on the line without exceeding 80 characters. We could assume that whitespaces had a size of 1, and our goal was to insert linebreaks after certain words in order to maximize the number of lines. Of course, this could be done really simply using a greedy algorithm.

Now for part B, the question is slightly different. We again have to format text using the 72-80 characters format described above (and given the same type of input) but this time, we are required to maximize the number of lines ending with the letter r. I know that this requires a table and we are to fill in this table dynamically. However, this is where I'm stuck. I know that the entry to a certain cell in the table xould be something along the lines of max{word_included_on_same_line, word_added_to_the_next_line} ... but no matter what I try to do with the table, I can't seem to derive a formula to fill it in (in order to maximize the number of lines ending with the letter r). Note that we do note have to maximize the overall number of lines, but simply the number of lines ending with r.

Any help would be really appreciated.. I've been stuck on this last question for severeal days, and now I'm running out of time - I was wondering if someone could provide some guidance as to how I can go about to create a table in order to solve this using a dynamic programming solution. (No code is needed - just to describe an algorithm)

Thanks - L.N

This post has been edited by LivingNightmare: 12 July 2010 - 07:29 PM

[macosxnerd101]

We're happy to help, but can you show us your efforts and give us a better idea of where you are stuck?

[LivingNightmare]

Well, this is the reccurence relation I came up with Let T[i, j, k] be the maximum number of lines that finish with r at some word i, on line j, starting at position k (between 0 - 80).


So I have that T[i,j,k] = T[i-1, j,k - length(word_i)] if pos < 72 and the current word fits on the line (where pos in an accumulator of the current position) - or T[i-1, j-1, pos] + (possibly 1) if pos < 72 and the line ends with r. We then start on a newline. - or T[i-1, j-1, pos] + (possibly 1) if 72 <= pos <= 80 and the line ends with r. We then start a newline. - And finally: = max{T[i-1,j,k-length(word_i), T[i-1, j-1, pos] + (possibly 1 if the line ends with r)} otherwise. This is supposed to be a piecewise function, but it's hard to describe it in plain text. Like I said, i only need to provide pseudocode, so exact code isn't needed.

I think that this is correct (although Im sure there are way better ways to do so). However if it is correct, then I'm good to go, because comming up with this was the hardest part. Please confirm/give advice if possible. I really appreaciate the help.

L.N

[LivingNightmare]

Well my assignment has passed, and I simply wrote what i had here and explained a bit. The more I explained, the more it seemed like it was a reasonable solution. Even though this assignment has passed, I was wondering if someone could still provide me with insight and an explanation on this question. It would really be appreciated

L.N