我最近有一個面試問題如下： 我們給出了一個單詞列表，我們要格式化它們以最大化回車次數，同時保持字母數在一個範圍內的每行。最大化＃回車算法（貪婪？）
例如，我們希望有一個範圍的5 - 每行10（含）的字母，一種解決方案是這樣的：
hello (5) cat (3)
另一個是這樣的：
hello cat (9) <- 1 for a space
因此，第一個解決方案是更好，因爲我們有1回車比0秒。
如果一個單詞不適合，它必須放在一個新的行。例如：
hello (5) people (6)
直覺對我來說這似乎是一個貪心算法問題，我們只要我們滿足每線約束的最低信返回。然而，這似乎太簡單了，我現在開始懷疑自己了，但我不能拿出一個貪婪不是最好的反例。
如果單詞按照它們出現的順序排列，那麼簡單的貪婪方法應該是最優的，因爲沒有理由不盡可能在序列中儘可能早地放置回車。
如果您可以更改單詞的順序，那麼這是一個更困難的問題，然後可以應用以下方法。
按字母數量降序對單詞進行排序。
分配一條線每個長度的話> = 5
對於長度< 5的話，它是一種反向多個二進制元素倉背襯問題，其中：
箱櫃具有最小容量5和最大容量10.
您必須將單詞放在容器中，以使容器數量達到最大。
這至少是一個NP完全問題，但是「我認爲」（更多的是因爲它在採訪中被問到）動態規劃公式可以被認爲是在僞多項式時間內解決它（像揹包問題） 。
編輯： IMO貪婪算法應該在最大容量至少等於最小容量的兩倍的情況下工作，就像在這種情況下一樣。
也許我對此並不清楚，但這些單詞必須按順序格式化。如果我們收到詞語「你好」，「世界」，「貓」，則必須放置回車符以保持這個順序。 – DillPixel
@DillPixel在這種情況下，它是一種簡單的貪婪方法，可以爲您提供解決方案，因爲沒有理由不盡可能在序列中儘早放置回車符。 –
如果允許「貓」（三個字母）在自己的行中，爲什麼你有最小範圍（5-10中的5）？ – justhalf
我沒有考慮到......我認爲最後一句話不在這些限制之下。但如果是這樣，那麼貪婪可能無法正常工作... – DillPixel
我想在這個範圍內應該沒有最小值。否則，這種情況是不可解決的：「牛蛙吃牛蛙」。在不違反最多10個字符的情況下，「吃」不能與任何單詞配對。除非輸入受限於在給定範圍條件的情況下始終有解決方案。 – justhalf