<p>好吧,这激起了我的好奇心,所以我用<code>abs(num_words - avg_words)**3</code>这个简单的不良启发写了一个动态规划算法。它应该和任何启发一起工作。以下是示例输出:</p>
<pre><code>>>> 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]
</code></pre>
<p><a href="http://pastebin.com/HQvfRCDr" rel="nofollow">Here</a>这是代码。尽管我建议你自己去实现它,做一个很好的练习!你知道吗</p>
<p>子问题是<code>R(n, i, j)</code>,也就是说:用<code>n</code>读数从<code>i</code>到<code>j</code>分割部分的最低坏处是什么?你知道吗</p>
<p>基本情况很简单:</p>
<pre><code>R(1, i, j) = heuristic(num words in sections i thru j, total words / total sections)
</code></pre>
<p>然后,对于递归,您可以从所有可能的方法中找到最佳的解决方案,以在左侧和右侧之间分割剩余的节数,以及放置该分区的最佳位置:</p>
<pre><code>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)
</code></pre>
<p>病理病例是指你的阅读量超过了部分:</p>
<pre><code>R(n, i, j) = infinity if n > j-i
</code></pre>
<p>从<code>n=1</code>到更高,再从<code>j-i = 1</code>到更高,再从<code>i=0</code>到更高构建解决方案。你知道吗</p>
<p>它最终有5个嵌套for循环,所以我不确定它是否有足够的效率,但它似乎做到了这一点。你知道吗</p>