Алгоритм группировки текста

Question

Учитывая произвольную строку текста, задача состоит в том, чтобы сгруппировать текст в отдельные разделы шаблона.Каждый раздел имеет разные параметры минимальной длины и максимальной длины.Решение можно считать оптимальным для сечения, если оно попадает в эти границы.Жадное решение может привести к тому, что некоторые разделы не будут соответствовать их минимумам, что означает, что решение в целом неприемлемо.

У меня проблемы с эффективностью построения алгоритма для этого.Кажется, что подход динамического программирования мог бы помочь, но до сих пор я не смог сформулировать его в терминах динамического программирования.У кого-нибудь есть какие-то подсказки по решению этой проблемы?

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.

В качестве примера давайте определим строку 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;

Answer 2

ОК, так вот специальный, непроверенный алгоритм.Если это нехорошо, возможно, это достаточно хорошо, чтобы заставить кого-то другого найти лучший ответ;

Давайте представим несколько пробных данных.Предположим, что ваш шаблон состоит из 6 разделов, которые имеют минимальные и максимальные ограничения:

1 - 12
13 - 25
5 - 7
6 - 7
5 - 5
10 - 25

, что означает, что вам потребуется строка длиной не менее 40 и не более 81 символа для удовлетворения ваших ограничений.И в этом заключается решение.Сначала вычислите таблицу следующим образом:

40 - 81
39 - 69
26 - 34
21 - 37
15 - 30
10 - 25

, в которой каждая строка дает общую длину строки, которая все еще может быть разбита на «слоты» в вашем шаблоне.В слот 1 вы помещаете текст таким образом, чтобы оставшиеся от 39 до 69 символов оставались для остальных слотов.В слот 2 вы помещаете текст так, чтобы у вас оставалось от 26 до 34 символов.И так далее.