テキストグループ化アルゴリズム

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もあります。 は、いくつかのセクションで構成されています。各セクションのには、許容される最小および最大文字数があります。この例では、セクションが2つしかないとします。s1とs2です。 S1は、1つの文字の最小と100 S2の最大を持っている私たちは、機能groupTextに私たちの文字列strのと私たちのテンプレートトンを渡す10文字の最小値と15の最大値を有します。 groupTextは配列を返し、各要素はセクションに対応するiとなります。たとえば、要素0はs1に対応します。要素の値は、セクションに割り当てられたテキストになります。

この例では、解決策があります。

s1text = "この"

s2text = "テストです。"

Answer 1

私が問題を正しく理解していれば、検索の必要はありません。最小長の合計と残っているものを合計長から差し引くだけです。何も残っていないまで続いので、ここでアドホック、テストされていないアルゴリズムはだ、OK

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

コードに...その最大までの各要素にこの金額を配布しています。それがうまくいかない場合は、他の誰かをより良い答えに導くのに十分かもしれません。

いくつかの試用データを用意しましょう。あなたの制約を満たすために、少なくとも40と最大で81文字の文字列を必要としていることを意味している

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

：あなたのテンプレートはとして6分を持っているセクション、最大の限界を有しているとします。そしてその中に解決策がある。各行は依然としてテンプレートに「スロット」を横切って分配することができる文字列の長さの合計を与える

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

た：まず、このようなテーブルを計算します。スロット1には、残りのスロットに残り39〜69文字の文字が残ります。スロット2には、26文字から34文字までのテキストを入力できます。等々。