把一个块状序列分成偶数个包裹？

Question

我有一个“块状”的项目序列，我想把它们分成一定数量的大小大致相等的包裹，同时保持包裹内容（以及包裹本身）的排序顺序。既然没有什么新鲜事，我猜我只是缺少这个问题的恰当名称。我的最终目标是用python实现算法，但我至少需要朝着正确的方向努力。你知道吗

问题是我有一篇课文，分成不同长度的部分，我想把它分成一系列公平的读物。当然，阅读的顺序必须保持不变。你知道吗

对于一些细节，我有2519节。最长1876字，最短7字。平均长度305字，中位长度242字。你知道吗

Answer 1

我不确定它是否确实解决了你的程序，但是在麻省理工开放式课程Introduction to Algorithms中，他们使用dynamic programming来解决行的最佳分割，这样文本就可以很好地沿着页面（'word-wrapping'）填充，类似于Latex所做的。见17分钟进入this video。你知道吗

该算法将给出保证最优分裂给定的一些函数，定义了一个罚款的基础上有多丑陋的线分裂。在讲座中，他们将这个丑陋的函数定义为(pagewidth - actual_linewidth)^3，但您可以定义自己的函数。该算法或多或少地尝试了所有不同的分裂可能性（以一种聪明的方式），并选择了最佳的一种。DP的主要要求是可以将问题划分为子程序，例如，可以基于n-1, n-2, ...字的先前解决方案来描述n字的解决方案。这些类型的DP算法通常是O(n^2)或O(n^3)，因此绝对不是NP难的。你知道吗

如果你对基本算法感兴趣，我强烈建议你看整个系列讲座，老师们都很棒。你知道吗

Answer 2

好吧，这激起了我的好奇心，所以我用abs(num_words - avg_words)**3这个简单的不良启发写了一个动态规划算法。它应该和任何启发一起工作。以下是示例输出：

>>> section_words = [100, 100, 100, 100, 100, 100, 40000, 100, 100, 100, 100]
>>> def heuristic(num_words, avg):
...     return abs(num_words - avg)**3
... 
>>> print_solution(solve(section_words, heuristic, 3))
Total=41000, 3 readings, avg=13666.67
Reading #1 (  600 words): [100, 100, 100, 100, 100, 100]
Reading #2 (40000 words): [40000]
Reading #3 (  400 words): [100, 100, 100, 100]
>>> print_solution(solve(section_words, heuristic, 5))
Total=41000, 5 readings, avg=8200.00
Reading #1 (  300 words): [100, 100, 100]
Reading #2 (  300 words): [100, 100, 100]
Reading #3 (40000 words): [40000]
Reading #4 (  200 words): [100, 100]
Reading #5 (  200 words): [100, 100]

>>> section_words = [7, 300, 242, 100, 115, 49, 563, 
                     1000, 400, 9, 14, 300, 200, 400, 
                     500, 200, 10, 19, 1876, 100, 200, 
                     15, 59, 299, 144, 85, 400, 600, 534, 200, 143, 15]
>>> print_solution(solve(section_words, heuristic, 10))
Total=9098, 10 readings, avg=909.80
Reading #1 (  649 words): [7, 300, 242, 100]
Reading #2 (  727 words): [115, 49, 563]
Reading #3 ( 1000 words): [1000]
Reading #4 (  723 words): [400, 9, 14, 300]
Reading #5 (  600 words): [200, 400]
Reading #6 (  729 words): [500, 200, 10, 19]
Reading #7 ( 1876 words): [1876]
Reading #8 (  902 words): [100, 200, 15, 59, 299, 144, 85]
Reading #9 ( 1000 words): [400, 600]
Reading #10 (  892 words): [534, 200, 143, 15]

>>> print_solution(solve(section_words, heuristic, 5))
Total=9098, 5 readings, avg=1819.60
Reading #1 ( 2376 words): [7, 300, 242, 100, 115, 49, 563, 1000]
Reading #2 ( 2023 words): [400, 9, 14, 300, 200, 400, 500, 200]
Reading #3 ( 1905 words): [10, 19, 1876]
Reading #4 ( 1302 words): [100, 200, 15, 59, 299, 144, 85, 400]
Reading #5 ( 1492 words): [600, 534, 200, 143, 15]

>>> print_solution(solve(section_words, heuristic, 3))
Total=9098, 3 readings, avg=3032.67
Reading #1 ( 3099 words): [7, 300, 242, 100, 115, 49, 563, 1000, 400, 9, 14, 300]
Reading #2 ( 3205 words): [200, 400, 500, 200, 10, 19, 1876]
Reading #3 ( 2794 words): [100, 200, 15, 59, 299, 144, 85, 400, 600, 534, 200, 143, 15]

Here这是代码。尽管我建议你自己去实现它，做一个很好的练习！你知道吗

子问题是R(n, i, j)，也就是说：用n读数从i到j分割部分的最低坏处是什么？你知道吗

基本情况很简单：

R(1, i, j) = heuristic(num words in sections i thru j, total words / total sections)

然后，对于递归，您可以从所有可能的方法中找到最佳的解决方案，以在左侧和右侧之间分割剩余的节数，以及放置该分区的最佳位置：

R(n, i, j) = the lowest badness out of
    R(1, i, i+1) + R(n-1, i+1, j)
    R(1, i, i+2) + R(n-1, i+2, j)
    ...
    R(1, i, j-1) + R(n-1, j-1, j)

    R(2, i, i+1) + R(n-2, i+1, j)
    R(2, i, i+2) + R(n-2, i+2, j)
    ...
    R(2, i, j-1) + R(n-2, j-1, j)

    ...
    ...

    R(n-1, i, i+1) + R(1, i+1, j)
    R(n-1, i, i+2) + R(1, i+2, j)
    ...
    R(n-1, i, j-1) + R(1, j-1, j)

病理病例是指你的阅读量超过了部分：

R(n, i, j) = infinity if n > j-i

从n=1到更高，再从j-i = 1到更高，再从i=0到更高构建解决方案。你知道吗

它最终有5个嵌套for循环，所以我不确定它是否有足够的效率，但它似乎做到了这一点。你知道吗

Answer 3

这会给你一个好的结果，一个“贪婪”的策略：

• 算出你努力争取的平均数，avg = total_words / num_readings。你知道吗
• 开始遍历各个部分，累积到目前为止的字数。你知道吗
• 如果你击中了一个精确的匹配，然后标记该部分并继续。你知道吗
• 否则，如果你要检查字数，选择是否包括下一节根据什么是更接近平均值，例如，如果你是20短，如果你不包括它，但100多，如果你这样做，然后把它遗漏。你知道吗

要做得更好，你需要一些启发。如果你把输入搞砸了，比如一个大的部分和许多小的部分，比如说

100 100 100 100 100 100 40000 100 100 100 100

如果你想把它分成5个部分，你希望你的输出是什么样的？我的算法会告诉你：

100 100 100 100 100 100
40000
100 100 100 100
0
0

您可以很容易地对其进行调整，以强制每个部分至少使用一个单词：

100 100 100 100 100 100
40000
100 100
100
100

但这可能不像这个选项那么“好”：

100 100 100
100 100 100
40000
100 100
100 100

是的，我建议你看看Bas建议的讲座。你必须调整一下启发式。例如，对于你来说，在一节中有更多的单词是可以的，而对于行打包来说，如果你再看一遍的话，那就太糟糕了。你知道吗