我有一个"块状"项目序列,我想分成一定数量的大致相等大小的宗地,同时保持宗地内容(和宗地本身)的排序顺序.由于在阳光下没什么新东西,我猜我只是缺少问题的正确名称.我的最终目标是算法的python实现,但我至少需要朝着正确的方向推进.
问题是我有一个文本,分为不同长度的部分,我想把它分成一系列公平的读数.当然,读数的顺序必须保持不变.
对于某些细节,我有2,519个部分.最长的是1,876个单词,最短的是7个单词.平均长度为305个字,中位数长度为242.
我不确定它是否完全解决了你的程序,但是在MIT OCW课程的算法入门中,他们使用动态编程来解决行的最佳分割,以便在页面上很好地填写文本(' 自动换行 ') ,类似于Latex所做的.观看此视频的 17分钟.
该算法将给出保证的最优分裂,给定一些函数,该函数基于线分裂的丑陋来定义惩罚.在讲座中,他们将此丑陋功能定义为(pagewidth - actual_linewidth)^3,但您可以定义自己的功能.算法比或多或少尝试所有不同的分裂可能性(以智能方式)并选择最佳的算法.DP的主要要求是可以将问题分成子程序,例如,n可以基于先前的n-1, n-2, ...单词解决方案来描述单词的解决方案.这些类型的DP算法通常是,O(n^2)或者O(n^3)绝对不是NP难.
如果您对基本算法感兴趣,我强烈建议您观看整个系列讲座,老师们很棒.