Kleinste zwei Summen von ganzen Zahlen in einem Array

Question

Ich habe ein Array mit ganzen Zahlen (sortiert oder unsortiert, je nachdem, was einfacher sein wird, aber hier werde ich es sortiert) ausgefüllt:

10,20,20,30,40

Was ich versuche, zu tun ist, zwei kleinste Summen dieser Zahlen zu bekommen. In diesem Fall sollte es 60 sein, denn:

10+20+30 = 60 und 20+40 = 60. Was ich versucht habe, ist, wenn ich Array sortiert habe, spalte Zahlen, die erste geht links, zweite rechts, links, rechts ... Aber ich bekomme nicht die kleinste Summe. In diesem Fall würde ich mit meinem Algorithmus folgende Summe erhalten:

10+20+40 = 70 und 20+30 = 50 was nicht sehr effektiv ist.

Nur damit Sie wissen, ich arbeite an einem Zeitmanagement-Algorithmus, also möchte ich die bestmöglichen Zeiten erreichen.

Answer 1

Es wäre N! Möglichkeit, eine Gruppe aus N Nummern auszuwählen, wenn keine Duplikate vorhanden sind. Generiere alle möglichen Gruppen. Die beste Gruppe hat die minimale Summe, die nicht weniger als die Hälfte der Summe ist, da die anderen Zahlen eine Summe nicht mehr als die Hälfte haben.

Answer 2

Ich denke, das ist im Geiste näher an das Fach Verpackung Problem. https://en.wikipedia.org/wiki/Bin_packing_problem

Der Greedy-Algorithmus gibt es für Ihren Testfall

Zuerst sortieren Sie Ihre Array

[40,30,20,20,10]

Initialise zwei leere Behälter

funktioniert gut

A = [] b = []

Entfernen Sie bei jedem Schritt das größte Element aus Ihrem Array und legen Sie es in den Behälter mit der kleinsten Summe (i f sie gleiche Summe haben, ist es in A gesetzt) ​​

Für Ihre Array funktioniert dies als

step 0: 
[40,30,20,20,10] 
A=[] B=[] 

step 1: 
[30,20,20,10] 
A=[40] B=[] 

step 2: 
[20,20,10] 
A=[40] B=[30] 

step 3: 
[20,10] 
A=[40] B=[30,20] 

step 4: 
[10] 
A=[40,20] B=[30,20] 

step 4: 
[] 
A=[40,20] B=[30,20,10] 

folgt Und Sie haben die gewünschte Antwort. Natürlich können Sie Sets finden, für die dies nicht funktioniert, es handelt sich um einen ungefähren Algorithmus. Zum Beispiel, [50,49,33,33,33]