algorithm - 最大化回车算法的#(贪心？)

Question

最近有一道面试题如下:我们得到了一个单词列表，我们想要格式化它们以最大化回车符的数量，同时将每行的字母数量保持在一个范围内。

例如，我们希望每行的字母范围为 5 - 10(含)，一种解决方案是:

hello (5)cat (3)

另一个是这样的:

hello cat (9) <- 1 for a space

所以第一个解决方案更好，因为我们有 1 个回车而不是第二个中的 0。

如果一个词不合适，它必须换行。例如:

hello (5)people (6)

在我看来，这似乎是一个贪心算法问题，只要满足每行最小字母限制，我们就会返回。然而，这似乎太简单了，我现在开始怀疑自己，但我想不出贪婪不是最好的反例。

Answer 1

如果要按照单词出现的顺序放置单词，那么简单的贪婪方法应该是最佳方法，因为没有理由不将回车符尽可能早地放在序列中。

如果允许改变单词的顺序，那么这是一个更难的问题，然后可以应用以下方法。

按照字母个数降序排列单词。

为长度 >= 5 的单词各分配一行。

对于长度 < 5 的单词，它是一个反向多个 bins bin backing 问题，其中:
箱子的最小容量为 5，最大容量为 10。
您必须将单词放入容器中，以使容器的数量最大化。

这至少是一个 NP 完全问题，但“我认为”(更确切地说是因为在采访中被问到)可以认为动态规划公式可以在伪多项式时间内解决它(如背包问题)。

编辑:IMO 贪婪算法应在最大容量至少等于最小容量的两倍的情况下工作，就像在这种情况下一样。