Cần một thuật toán để tách một chuỗi số

Question

Sau một vài đêm bận rộn, đầu của tôi không hoạt động tốt, nhưng điều này cần được khắc phục ngày hôm qua, vì vậy tôi hỏi cộng đồng SO được làm mới hơn.

Tôi có một chuỗi số. Ví dụ:

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

tôi cần phải chia loạt bài này thành ba phần để tổng các con số trong tất cả các bộ phận càng gần càng tốt. Thứ tự của các số cần phải được duy trì, vì vậy phần đầu tiên phải bao gồm các số X đầu tiên, số thứ hai - của các số Y tiếp theo và thứ ba - của bất kỳ số nào còn lại.

Thuật toán để làm điều này là gì?

(Lưu ý: vấn đề thực tế là sắp xếp các đoạn văn bản có chiều cao khác nhau thành ba cột. Đoạn văn phải duy trì trật tự (dĩ nhiên) và chúng không thể chia làm hai phần.)

Answer 1

tiên, chúng ta sẽ cần phải xác định mục tiêu thì càng tốt:

Giả sử số tiền một phần là A1, A2, A3, Chúng tôi đang cố gắng để giảm thiểu | A-A1 | + | A-A2 | + | A-A3 |. A là giá trị trung bình: A = (A1 + A2 + A3)/3.

Vì vậy, chúng tôi đang cố gắng giảm thiểu | A2 + A3-2A1 | + | A1 + A3-2A2 | + | A1 + A2-2A3 |.

Cho S biểu thị tổng (hằng số): S = A1 + A2 + A3, vì vậy A3 = S-A1-A2.

Chúng tôi đang cố gắng để giảm thiểu:

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

biểu thị chức năng này như f, chúng tôi có thể làm hai vòng O (n^2) và theo dõi tối thiểu:

Cái gì như:

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

Tôi tin rằng điều này có thể được giải quyết với a dynamic programming algorithm for line breaking được phát minh bởi Donald Knuth để sử dụng trong TeX.

Answer 3

tìm tổng số và tổng tích lũy của chuỗi.

được a = sum/3

sau đó xác định vị trí gần một, 2 * a trong tổng tích lũy mà chia danh sách của bạn thành ba phần bằng nhau.

Answer 4

Theo câu trả lời của Aasmund Eldhuset, trước đây tôi đã trả lời câu hỏi này về SO.

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

algo này không dựa vào kích thước dòng tối đa nhưng chỉ đưa ra một cắt tối ưu.

tôi sửa đổi nó để làm việc với vấn đề của bạn:

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 

kết quả tôi nhận được là:

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

Hy vọng nó giúp

Answer 5

phép nói rằng p là mảng của bạn độ cao đoạn;

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

Bạn sẽ nhận được chỉ mục bắt đầu của chuỗi thứ 2 và thứ 3. Lưu ý loại hình này của mã giả :)