Serve un algoritmo per dividere una serie di numeri

Question

Dopo alcune notti intense la mia testa non funziona così bene, ma questo deve essere corretto ieri, quindi chiedo alla comunità più aggiornata di SO.

Ho una serie di numeri. Ad esempio:

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

devo dividere questa serie in tre parti così la somma dei numeri in tutte le parti è il più vicino possibile. L'ordine dei numeri deve essere mantenuto, quindi la prima parte deve essere composta dai primi numeri X, dal secondo - dei prossimi numeri Y e dal terzo - di ciò che rimane.

Quale sarebbe l'algoritmo per fare questo?

(Nota: il problema reale è di organizzare paragrafi di testo di diverse altezze in tre colonne paragrafi deve mantenere l'ordine (ovviamente) e non può essere diviso a metà Le colonne deve essere uguale altezza possibile...)

Answer 1

In primo luogo, abbiamo bisogno di definire l'obiettivo migliore:

Supponiamo le somme parziali sono A1, A2, A3, stiamo cercando di ridurre al minimo | A-A1 | + | A-A2 | + | A-A3 |. A è la media: A = (A1 + A2 + A3)/3.

Pertanto, stiamo cercando di ridurre a icona | A2 + A3-2A1 | + | A1 + A3-2A2 | + | A1 + A2-2A3 |.

Sia S la somma (che è costante): S = A1 + A2 + A3, quindi A3 = S-A1-A2.

stiamo cercando di ridurre al minimo:

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

Indicando questa funzione come f, possiamo fare due anelli O (n^2) e tenere traccia del minimo:

Qualcosa di simile:

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 
    } 
} 

Answer 2

Credo che questo possa essere risolto con a dynamic programming algorithm for line breaking inventato da Donald Knuth per l'utilizzo in TeX.

Answer 3

trovare somma e somma cumulativa della serie.

ottenere una somma =/3

quindi individuare più vicino a, 2 * a nella somma cumulativa che divide la lista in tre parti uguali.

Answer 4

In seguito alla risposta di Aasmund Eldhuset, in precedenza ho risposto a questa domanda su SO.

Word wrap to X lines instead of maximum width (Least raggedness)

Questa algo non si basa sulla dimensione massima linea ma solo dà un taglio ottimale.

ho modificato per funzionare con il vostro problema:

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 

il risultato che ottengo è:

[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]] 

Speranza che aiuta

Answer 5

permette di dire p è la matrice del paragrafo altezze;

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; 
} 

Si otterrà l'indice iniziale della 2a e 3a sequenza. Nota la sua sorta di pseudo codice :)