5

在您认为它重复之前（有很多问题询问如何拆分长字符串而不破坏单词）请记住我的问题有点不同：顺序并不重要，我必须适合单词才能使用每一行越多越好。

我有一组无序的单词，我想在不使用超过 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)

我该怎么办？

4

2 回答 2

5

这是装箱问题；该解决方案是 NP-hard，尽管存在非最优启发式算法，主要是首次拟合递减和最佳拟合递减。有关实现，请参见https://github.com/type/Bin-Packing。

于 2013-05-07T09:05:56.730 回答
2

非最优离线快速一维装箱 Python 算法

def binPackingFast(words, limit, sep=" "):
    if max(map(len, words)) > limit:
        raise ValueError("limit is too small")
    words.sort(key=len, reverse=True)
    res, part, others = [], words[0], words[1:]
    for word in others:
        if len(sep)+len(word) > limit-len(part):
            res.append(part)
            part = word
        else:
            part += sep+word
    if part:
        res.append(part)
    return res

表现

经过测试/usr/share/dict/words（由 提供words-3.0-20.fc18.noarch），它可以在我的慢速双核笔记本电脑上在一秒钟内完成 50 万字，在以下参数下效率至少为 90%：

limit = max(map(len, words))
sep = ""

我得到limit *= 1.592%，limit *= 2我得到 96%（相同的执行时间）。

最佳（理论）值计算如下：math.ceil(len(sep.join(words))/limit)

没有高效的装箱算法可以保证做得更好

资料来源： http: //mathworld.wolfram.com/Bin-PackingProblem.html

故事的道德启示

虽然找到最佳解决方案很有趣，但我认为在大多数情况下，将此算法用于一维离线装箱问题会更好。

资源

笔记

于 2013-05-07T18:40:40.377 回答