algorithm - 我们可以使用贪心算法而不是动态规划来解决 "printing neatly"问题吗？

Question

《算法导论》一书中的“打印整齐”问题是通过动态规划解决的。是问题5.3，找到了解决方案here

我认为这个问题可以通过贪心算法简单地解决。只需在每行中放置尽可能多的单词，直到放不下下一个单词，然后换行。

有人可以帮助我了解此解决方案是否足够吗？ (贪心算法)

问题来了:整齐地打印

考虑在打印机上整齐打印段落的问题。输入文本是 n 个单词的序列，长度为 l1,l2,...,ln，以字符为单位。我们想把这个段落整齐地打印在多行上，每行最多包含 M 个字符。我们的“整洁”标准如下。如果给定行包含单词 i 到 j，并且我们在单词之间只留一个空格，则行尾的额外空格字符数是 M 与单词中的字符总数加上它们之间的空格之差。我们希望在除最后一行之外的所有行中，最小化行尾额外空格字符数的立方体的总和。给出一个动态规划算法在打印机上整齐地打印一段 n 个单词。分析算法的运行时间和空间要求。

Answer 1

不，因为贪婪算法经常出现这种情况，现在的短视决策(决定当前行有多少单词)最终会在以后迫使更高的成本。例如，假设我们每行可以有 10 个字符。

贪心法

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)

贪婪的解决方案将更多的单词打包到第一行，但实际上会产生更高的总解决方案成本。