python - 拆分长字符串而不中断单词填充行

Question

在你认为它是重复的之前(有很多问题询问如何在不打断单词的情况下拆分长字符串)请记住我的问题有点不同:顺序并不重要，我必须适应单词为了尽可能地利用每一行。

我有一组无序的单词，我想在不使用超过 253 个字符的情况下组合它们。

def compose(words):
    result = " ".join(words)
    if len(result) > 253:
        pass # this should not happen!
    return result

我的问题是我想尽可能地填满这条线。例如:

words = "a bc def ghil mno pq r st uv"
limit = 5 # max 5 characters

# This is good because it's the shortest possible list,
#   but I don't know how could I get it
# Note: order is not important
good = ["a def", "bc pq", "ghil", "mno r", "st uv"]

# This is bad because len(bad) > len(good)
#   even if the limit of 5 characters is respected
# This is equivalent to:
#   bad  = ["a bc", "def", "ghil", "mno", "pq r", "st uv"]
import textwrap
bad = textwrap.wrap(words, limit)

我该怎么办？

Answer 1

这是 bin packing problem ;该解决方案是 NP-hard，尽管存在非最佳启发式算法，主要是先拟合递减和最佳拟合递减。参见 https://github.com/type/Bin-Packing用于实现。