我最近有一个面试问题，如下所示：我们得到了一个单词列表，我们希望对它们进行格式化，以最大限度地增加回车次数，同时将每行的字母数保持在一个范围内。
例如，我们希望每行包含5-10个字母，一种解决方案是：
你好（5）猫（3）
另一个是：
你好猫（9）<-1表示空间
因此，第一种解决方案更好，因为我们有1个回车，而第二种是0。
如果一个单词不合适，就必须把它放在新行上。例如：
你好（5）人（6）
在我看来，这似乎是一个贪婪的算法问题，只要满足每行最小字母的约束，我们就会返回。然而，这似乎太简单了，我现在开始怀疑自己，但我无法想出贪婪不是最好的反例。
如果单词要按照它们出现的顺序放置，那么简单的贪婪方法应该是最优的，因为没有理由不尽早在序列中放置回车。
如果你被允许改变单词的顺序，那么这是一个更困难的问题，然后可以应用以下方法。
按字母数的降序对单词进行排序。
为长度>=5的单词各指定一行。
对于长度<5，这是一个反向多仓仓备份问题，其中：
垃圾箱的最小容量为5，最大容量为10。
你必须把单词放在箱子里，这样箱子的数量才能最大化。
这至少是一个NP完全问题，但"我认为"（因为在一次采访中被问到了这一点）可以想到一个动态规划公式，它可以在伪多项式时间内解决它（就像背包问题）。
编辑：IMO贪婪算法应在最大容量至少等于最小容量的两倍的情况下工作，就像在这种情况下一样