我们可以解决“整齐打印”吗？使用贪婪算法而不是动态编程的问题？ [英] Can we solve the "printing neatly" problem using a greedy algorithm rather than dynamic programming?

问题描述

通过动态编程解决了《算法入门》一书中的整齐打印问题。是问题5.3，并且找到了解决方案此处

The "printing neatly" problem in the "introductions to algorithms" book is solved via dynamic programming. It's Problem 5.3 and the solution is found here

我认为可以通过贪婪算法简单地解决此问题。只需在每行中尽可能多地放入单词，直到您无法容纳下一个单词，然后移至新行即可。

I think this problem could be simply solved by a greedy algorithm. Just put as many words per line as possible intil you can't fit the next word and so move to a new line.

有人可以帮助我了解此解决方案是否是足够 ？ （贪婪的算法）

Can someone help me understand if this solution is enough ? (the greedy algo)

这里是问题：整齐地打印

Here's the problem: Printing neatly

考虑整齐地打印段落的问题打印机。输入文本是由n个单词组成的序列，长度为l1，l2，...，ln，以字符为单位。我们希望在多行中整齐地打印此段，每行最多包含M个字符。我们的整洁标准如下。如果给定的行包含从i到j的单词，并且我们在单词之间恰好留出一个空格，则该行末尾的多余空格字符数是M与单词中的字符总数加上它们之间的空格之差。我们希望将除最后一行以外的所有行的总和最小化，以减少行尾多余空格的数量。提供一种动态编程算法，以在打印机上整齐地打印n个单词的段落。分析算法的运行时间和空间要求。

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 and we leave exactly one space between words, the number of extra space characters at the end of the line is the difference between M and the total number of characters in the words plus the spaces between them .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.

推荐答案

否，因为贪婪算法通常是短视的现在的决定（决定当前行的单词数）最终迫使更高的成本。例如，假设我们每行可以有10个字符。

No, because as is often the case with greedy algorithms, short sighted decisions now (deciding how many words for the current line) end up forcing higher cost later. For example, suppose we can have 10 chars per line.

贪心解决方案

xx xxx xx    cost = 1
xxxxx        cost = 125
xxxxx        cost = 0 (last line)

更好的解决方案

xx xxx       cost = 64
xx xxxxx     cost = 8
xxxxx        cost = 0 (last line)

贪婪的解决方案在第一行添加了更多单词，但这实际上会产生更高的总解决方案成本。

The greedy solution packs more words onto the first line, but that actually produces a higher total solution cost.

这篇关于我们可以解决“整齐打印”吗？使用贪婪算法而不是动态编程的问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！