I was going through this question : Printing Neatly (15.2, Cormen) Consider the problem of neatly printing a paragraph on a printer. The input text is a sequence of n words of lengths l1, l2, . . . , ln, measured in characters. We want to print this paragraph neatly on a number of lines that hold a maximum of M characters each. Our criterion of “neatness” is as follows. If a given line contains words i through j, where i ≤ j , and we leave exactly one space between words, the number of extra space characters at the end of the line is M − j +i − Sum(lk)(from k = i to j) , which must be nonnegative so that the words fit on the line. We wish to minimize the sum, over all lines except the last, of the cubes of the numbers of extra space characters at the ends of lines. Give a dynamic-programming algorithm to print a paragraph of n words neatly on a printer. Analyze the running time and space requirements of your algorithm.
I don't have any problem solving this question using Dynamic Programming, but can we solve this problem using simple greedy approach of fitting maximum words in a line taking care of all the constraints mentioned, can anybody provide a counter example where this greedy approach is not optimal? Please Help! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/G-FzuzkIv-0J. To post to this group, send email to algogeeks@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.
