Heres a nice little problem that has been keeping me up for days.
We have a set of n words (where a word is anything between two spaces).
Our printer only allows M characters per line included the spaces
between the lines.
We want to provide the optimal way of outputting our text with an even
spread of remaining spaces at each line. We can assume that no word is
longer than M.
The heuristic we use is the number of remaining spaces s^3 or s to the
power of 3.
I have already guessed that this is probably best solved with a dynamic
programming algorithm and the recursive definition to provide this is.
optSolution({o..n}) = the optimal solution after attaching the next word
to the current line (if it fits) OR the optimal solution after putting
the next word on a new line below the current one. Whichever of those
choices produces the lowest total cost when called recursively.
So far I am fine, now for the tricky part where I feel that I am stuck
in the same trail of thought and not getting anywhere.
*How do I construct this solution bottom up?*
of course I could do it using memoization thus using the recursion but
'tweaking' it by storing results in tables also. But I am quite sure
there is a better way to do it... and I can guess that memoizing this
algorithm will get quite messy.
I don't want the solution handed, just some good pointers to get me
going in the right direction, believe it or not my girlfriend is not
that helpful when it comes to discussing algorithms :-)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
