文本分組算法

給定一個任意字符串的文本，任務是將文本分組爲模板的不同部分。每個部分具有不同的最小長度和最大長度參數。只要一個解決方案落在這些範圍內，就可以認爲解決方案是最優的。貪婪的解決方案可能會導致某些部分達不到最低要求，這意味着解決方案作爲一個整體是不可接受的。文本分組算法

我很難有效地構造一個算法來做到這一點。似乎動態編程方法可能會有所幫助，但到目前爲止，我還沒有能夠用動態編程術語來解決它。有沒有人有解決這個問題的任何線索？

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和我們的模板噸到功能groupText。 groupText必須返回一個數組，其中每個元素對應於一個段。例如，元素0將對應於s1。元素的值將是已分配給該部分的文本。

在這個例子中，一個解決方案可能是。

s1text = 「此」

s2text = 「是一個測試」。

來源

2012-03-14 tabdulla

你想要做的一個例子會幫助我們更好地理解你的問題。尤其是輸入和期望輸出的一個例子。 – 2012-03-14 19:43:31

這聽起來像是一個線性編程問題。 – mindvirus 2012-03-14 19:54:06

@HighPerformanceMark - 我已經添加了一個例子。讓我知道這是否有幫助。感謝您的反饋。 – tabdulla 2012-03-14 19:57:21

如果我正確地理解了問題，則不需要任何搜索......只需從總長度中減去最小長度的總和，剩下的就是要分配的數量。然後，直到沒有剩下分發本金額每一個元素到其最大...代碼

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;

來源

2012-03-14 20:17:47 6502

OK，所以這裏是一個特設的，未經測試的算法。如果它不好，也許這足以讓別人更好地回答問題;

讓我們有一些試用數據。假設你的模板包括6個部分，其中有最小，最大限制爲：

這意味着你將需要至少40和最多81個字符的字符串，以滿足您的約束。解決方案就在於此。首先，計算像這樣的表：

，其中每行給出的字符串的總長度仍可以跨越「插槽」在您的模板進行分區。在插槽1中放置文本，以便剩下的插槽仍有39到69個字符。在插槽2中放置文字，以便您仍然有26到34個字符。等等。

來源

2012-03-14 20:20:50

文本分組算法

回答

相關問題