需要一个算法来分割一系列数字

在几个忙碌的夜晚之后，我的大脑不太好工作，但这需要在昨天修复，所以我要求更刷新的so社区。

我有一串数字。例如:

1,5,7,13,3,3,4,1,8,6,6,6

我需要把这个级数分成三部分，以便所有部分的数字之和尽可能接近。数字的顺序需要保持，所以第一部分必须由第一个X数字组成，第二部分由接下来的Y数字组成，第三部分由剩下的数字组成。

做这个的算法是什么?

(注:实际问题是将不同高度的文本段落排列成三列。段落必须保持顺序(当然)，它们不能被分成两半。)

首先，我们需要更好地定义目标:

假设部分和为A1,A2,A3，我们试图最小化|A-A1|+|A-A2|+|A-A3|。A为平均值:A=(A1+A2+A3)/3.

因此，我们试图最小化|A2+A3-2A1|+|A1+A3-2A2|+|A1+A2- 2a3 |

设S表示和(常数):S=A1+A2+A3，因此A3=S-A1-A2。

我们试图最小化:

| A2 + S-A1-A2-2A1 | + | A1 + S-A1-A2-2A2 | + | A1 + A2-2S + 2 A1 + 2 A2 | = | S-3A1 | + | S-3A2 | + | 3 A1 + SA2-2S |

表示这个函数为f，我们可以做两个循环O(n^2)并跟踪最小值:

类似:

for (x=1; x<items; x++)
{
    A1= sum(Item[0]..Item[x-1])
    for (y=x; y<items; y++)
    {
        A2= sum(Item[x]..Item[y-1])
        calc f, if new minimum found -keep x,y
    }
}

find sum and cumulative sum of series.

get a= sum/3

然后在累加和中找到最近的a, 2*a，该累加和将列表分成三个相等的部分。

假设p是段落高度数组;

int len= p.sum()/3;   //it is avarage value
int currlen=0;
int templen=0;
int indexes[2]; 
int j = 0;
for (i=0;i<p.lenght;i++)
{
    currlen = currlen + p[i];
    if (currlen>len)
    {
        if ((currlen-len)<(abs((currlen-p[i])-len))
        { //check which one is closer to avarege val
            indexes[j++] = i;
            len=(p.sum()-currlen)/2         //optional: count new avearege height from remaining lengths
            currlen = 0;
        }
        else
        {
            indexes[j++] = i-1;
            len=(p.sum()-currlen)/2
            currlen = p[i];
        }
    }
    if (j>2)
        break;
}

将得到第2和第3个序列的起始索引。注意它的伪代码类型:)

我相信这可以用Donald Knuth发明的用于TeX的动态规划断行算法来解决。

根据Aasmund Eldhuset的回答，我之前在SO上回答过这个问题。

换行到X行而不是最大宽度

该算法不依赖于最大行大小，而只是给出最佳切割。

我修改了它来解决你的问题:

L=[1,5,7,13,3,3,4,1,8,6,6,6]
def minragged(words, n=3):

P=2
cumwordwidth = [0]
# cumwordwidth[-1] is the last element
for word in words:
    cumwordwidth.append(cumwordwidth[-1] + word)
totalwidth = cumwordwidth[-1] + len(words) - 1  # len(words) - 1 spaces
linewidth = float(totalwidth - (n - 1)) / float(n)  # n - 1 line breaks
print "number of words:", len(words)
def cost(i, j):
    """
    cost of a line words[i], ..., words[j - 1] (words[i:j])
    """
    actuallinewidth = max(j - i - 1, 0) + (cumwordwidth[j] - cumwordwidth[i])
    return (linewidth - float(actuallinewidth)) ** P
"""
printing the reasoning and reversing the return list
"""
F={} # Total cost function
for stage in range(n):
    print "------------------------------------"
    print "stage :",stage
    print "------------------------------------"
    print "word i to j in line",stage,"ttTotalCost (f(j))"
    print "------------------------------------"

    if stage==0:
        F[stage]=[]
        i=0
        for j in range(i,len(words)+1):
            print "i=",i,"j=",j,"ttt",cost(i,j)
            F[stage].append([cost(i,j),0])
    elif stage==(n-1):
        F[stage]=[[float('inf'),0] for i in range(len(words)+1)]
        for i in range(len(words)+1):
                j=len(words)
                if F[stage-1][i][0]+cost(i,j)<F[stage][j][0]: #calculating min cost (cf f formula)
                    F[stage][j][0]=F[stage-1][i][0]+cost(i,j)
                    F[stage][j][1]=i
                    print "i=",i,"j=",j,"ttt",F[stage][j][0]            
    else:
        F[stage]=[[float('inf'),0] for i in range(len(words)+1)]
        for i in range(len(words)+1):
            for j in range(i,len(words)+1):
                if F[stage-1][i][0]+cost(i,j)<F[stage][j][0]:
                    F[stage][j][0]=F[stage-1][i][0]+cost(i,j)
                    F[stage][j][1]=i
                    print "i=",i,"j=",j,"ttt",F[stage][j][0]
print 'reversing list'
print "------------------------------------"
listWords=[]
a=len(words)
for k in xrange(n-1,0,-1):#reverse loop from n-1 to 1
    listWords.append(words[F[k][a][1]:a])
    a=F[k][a][1]
listWords.append(words[0:a])
listWords.reverse()
for line in listWords:
    print line, 'tt',sum(line)
return listWords

我得到的结果是:

[1, 5, 7, 13]       26
[3, 3, 4, 1, 8]         19
[6, 6, 6]       18
[[1, 5, 7, 13], [3, 3, 4, 1, 8], [6, 6, 6]]

希望有所帮助

相关内容

最新更新

热门标签：