Wie teilt man Array in Gruppen mit der kleinsten Differenz auf?

Question

Ich habe Array von ganzen Zahlen, ich muss sie in unbekannter Anzahl von Gruppen mit minimalen Unterschied in der Summe jeder Gruppe sortieren.

Beispiel:

Array: 2, 1, 4, 7, 1, 2, 6, 8 
Number of groups = 3 
Result: 
Group 1 – 8, 2 = 10 
Group 2 – 7, 2, 1 = 10 
Group 3 – 6, 4, 1 = 11 

Gibt es zu jeder alghoritham dieses Problem zu lösen? Ich stecke fest.

Answer 1

Erstens, wenn die Anzahl der Gruppen 2 ist reduziert dies auf die Teilmenge Summe Problemvariante das Partitionsproblem. Dies beweist, dass das Problem NP-schwer ist, also sollten Sie nicht versuchen, einen effizienten Algorithmus zu finden.

Da es mindestens exponentiell ist, können Sie auch einfach alle Permutationen generieren und die besten auswählen. Ich weiß, dass einige Leute nicht mögen Rekursion, aber es ist hier wirklich nützlich für Aufzählen der Gruppe Möglichkeiten:

recfunc(array, groups): 
    if array is empty 
     return an array containing the element groups 
    else 
     groupsList = empty array 
     foreach aGroup in groups 
      element = array[0] 
      groupsList += recfun(array - element, groups where aGroup adds element) 
     return groupsList 

Dieser Algorithmus eine Liste aller Möglichkeiten schaffen. Es ist ziemlich ineffizient, sollte aber nicht zu schwer für Sie sein. Von hier aus gehen Sie einfach durch die Liste und berechnen Sie, ob die Summe der Gruppen das Minimum der Liste ist.