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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.