javascript - 文本分组算法

Question

给定任意文本字符串，任务是将文本分组到模板的单独部分。每个部分都有不同的最小长度和最大长度参数。只要解决方案落在这些范围内，就可以认为该解决方案对于某个部分是最佳的。贪婪的解决方案可能会导致某些部分不满足其最小值，这意味着解决方案作为一个整体是 Not Acceptable 。

我无法有效地构建算法来执行此操作。似乎动态编程方法可能会有所帮助，但到目前为止，我还不能用动态编程术语来表达它。有没有人有解决这个问题的线索？

function groupText(str, template)
Inputs:
 str: a string of text
 template: array of JavaScript objects. 
           One object per section that describes the min/max amount of text allowed
Output:
 array: each element corresponds to one section. 
        The value of the element is the text that is in the section.

例如，让我们定义一个等于“This is a test”的字符串 str。我们还有一个模板t。 t 由几个部分组成。每个部分 s 都有允许的最小和最大字符数。假设这个例子只有两个部分:s1 和 s2。 s1 最少 1 个字符，最多 100 个字符。s2 最少 10 个字符，最多 15 个字符。我们将字符串 str 和我们的模板 t 到函数 groupText。 groupText 必须返回一个数组，每个元素 i 对应一个部分。例如，元素 0 将对应于 s1。元素的值将是分配给该部分的文本。

在这个例子中，一个解决方案可能是。

s1text = "这个"

s2text = "是一个测试。"

Answer 1

如果我正确理解了问题，则无需任何搜索...只需从总长度中减去最小长度之和，剩下的就是要分配的数量。然后将这个数量分配给每个元素，直到它的最大值为止......在代码中

var minsum = 0;
for (vsr i=0; i < sections.length; i++)
    minsum += sections[i].min_size;
var extra = text.length - minsum;
if (extra < 0) return null; // no solution
var solution = [];
for (var i=0; i < sections.length; i++)
{
    var x = sections[i].min_size + extra;
    if (x > sections[i].max_size)
        x = sections[i].max_size;
    solution.push(x);
    extra -= x - sections[i].min_size;
}
if (extra > 0) return null; // no solution
return solution;