Подтвердить что ты не робот

Нужен алгоритм разбиения ряда чисел

После нескольких напряженных ночей моя голова работает не так хорошо, но это нужно зафиксировать вчера, поэтому я спрашиваю об обновленном сообществе SO.

У меня есть серия чисел. Например:

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

Мне нужно разбить эту серию на три части, чтобы сумма чисел во всех частях была как можно ближе. Порядок номеров должен быть сохранен, поэтому первая часть должна состоять из первых X чисел, вторая - из следующих Y чисел, а третья - того, что осталось.

Каким будет алгоритм для этого?

(Примечание: фактическая проблема заключается в том, чтобы расположить текстовые абзацы разной высоты на три столбца. Пункты должны поддерживать порядок (разумеется), и они не могут быть разделены пополам. Столбцы должны быть как можно более высотой.)

4b9b3361

ОТВЕТЫ

Ответ 1

Во-первых, нам нужно лучше определить цель:

Предположим, что частичные суммы равны 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.

Мы пытаемся свести к минимуму:

| А2 + S-A1-A2-2A1 | + | А1 + С-А1-A2-2A2 | + | А1 + A2-2S + 2A1 + 2A2 | = | S-3A1 | + | S-3A2 | + | 3A1 + 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
    }
}

Ответ 2

найдите сумма и суммарную сумму.

получить a = sum/3

затем найдите ближайший a, 2 * a в суммарной сумме, которая делит ваш список на три равные части.

Ответ 4

Предположим, что 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;
}

Вы получите начальный индекс второй и третьей последовательности. Обратите внимание на его псевдокод:)

Ответ 5

После ответа 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,"\t\tTotalCost (f(j))"
    print "------------------------------------"


    if stage==0:
        F[stage]=[]
        i=0
        for j in range(i,len(words)+1):
            print "i=",i,"j=",j,"\t\t\t",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,"\t\t\t",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,"\t\t\t",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, '\t\t',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]]

Надеюсь, что это поможет