2012-04-04 5 views
0

Ich habe vier Arrays der Größe 2^N wo N = 25. Die Elemente von Arrays wurden von meinem Algorithmus generiert. Diese sind sortiert, enthalten aber Zahlen. Jetzt muss ich jedes Element von array1 nehmen und Elemente von array2, array3, array4 so auswählen, dass die Summe von ihnen minimal sein sollte (wenn ich Sum sage, kann ich a1 [k] + -a2 [j] + - a3 [m] nehmen + -a4 [t]. ich denke, es zu K Dimension verschmelzen Problem ähnlich ist. Kann jemand Punkt in der Literatur/Implementierung/Heuristik für das gleiche zu tun. Grüße, AllahbakshMatch Drei oder mehr Nächste Zahlen von Arrays

+0

1. Ein Beispiel wird sehr hilfreich sein. 2. Sie können das ± -Zeichen verwenden. –

+1

Was Sie in Wörtern fragen ist trivial - nehmen Sie die minimalen Elemente von Array2, 3 und 4, unabhängig von dem Element von Array1, dann wird auch die Summe minimal sein. Aber ich vermute, du willst etwas anderes wissen. –

Antwort

0

Schritt 1 für array1 [k], finden eine Reihe in array2 oder array3 oder array4 so dass ihr Modul näher an array1 [k].

eg . 
array1 = {1, 3, 67} 
array2 = {-31, 7, 47} 
array3 = {-1, 2, 10} 
array4 = {14, 15, 66} 

For array1[0] (ie. 1), the number closest to it is in array3 and its -1 as mod(-1) = 1 

Schritt 2 Dann finden Sie von den verbleibenden 2 Arrays ein Paar Zahlen, die näher beieinander liegen. (Wiederum betrachten Modul)

eg . 
array2 = {-31, 7, 47} 
array4 = {14, 15, 66} 

Closest elements are 7 and 14 with -7 + 14 = 7. 

Schließlich Sie min (a1 [k] + a2 [j] + - a3 [m] + - a4 [t]) erhalten von allen 4-Arrays.

+1

Also für 1 von Array1 ergibt dies: 1 - 1 - 7 + 14 = 7? Aber Sie können es besser machen: 1 + 7 + 10 - 14 = 4. – Henrik

+0

Dies wird die Lösung exponentiell sprengen. Ich denke, der brutale Weg, dies zu tun, ist es, es in eine Schleife zu bringen. Also 4 für eine Schleife für vier Arrays, die eine große Rechenleistung benötigen, wenn N zunimmt. Gibt es einen heuristischen Algorithmus für die KDM-Zusammenführung? –

+0

@ Henrick: guter Fang. Ich muss den Ansatz noch einmal überprüfen. –

0

Ich denke, dieses Problem könnte in O (n) gelöst werden, füge alle Arrays in Vereinigungsmenge zusammen, so zweiten Wert wird Array-Nummer sein. Iterate durch und auf jeder Iteration Form Antwort von 4 Werten, auf jedem Schritt maximale Distanz zwischen ausgewählten Zahlen berechnen -> diesen Wert minimieren.
Init-Ergebnis-Array mit den kleinsten Zahlen aus jedem Array.

public Integer[] findClosest(int[][] unionSet, Integer[] result) { 

    for (int i = 0; i < unionSet.length; i++) { 
     int value = unionSet[i][0]; 
     int position = unionSet[i][1]; 
     int currentDistance = getDistance(result); 
     Integer[] temp = Arrays.copyOf(result, result.length); 
     temp[position] = value; 
     int newDistance = getDistance(temp); 
     if (newDistance <= currentDistance) { 
      result = temp; 
     } 
    } 
    return result; 
} 

private int getDistance(Integer[] result) { 
    int max = 0; 
    int min = 0; 
    for (int i = 1; i < result.length; i++) { 
     if (result[i] != null) { 
      if (result[i] > result[max]) { 
       max = i; 
      } 
      if (result[min] != null && result[i] < result[min]) { 
       min = i; 
      } 
     } 
    } 

    return Math.abs(result[max] - result[min]); 
} 
Verwandte Themen