Hallo,
wie gesagt würde ich gerne ein Array aus Zahlen in 4 möglichst ähnliche Teile aufteilen. Ich finde bei Google allerdings nur Beispiele für das normale Partitionsproblem mit 2 Teilen. Hier mein Ansatz dafür:
Funktioniert das so überhaupt noch mit 4 Teilen? Also wenn ich 2 Zahlen berechne, die möglichst nah bei der viertel Gesamtsumme sind.
Oder ist das einfacher mit einem anderen Algorithmus (Backtracking oder so?) zu lösen? Muss nicht effizient sein, Hauptsache es funktioniert.
Vielen Dank schonmal.
wie gesagt würde ich gerne ein Array aus Zahlen in 4 möglichst ähnliche Teile aufteilen. Ich finde bei Google allerdings nur Beispiele für das normale Partitionsproblem mit 2 Teilen. Hier mein Ansatz dafür:
Java:
import java.io.*;
import java.util.*;
public class SplitIntArray {
private int aNumbers[];
private int sum;
private BitSet bset;
private int aS[];
public static void main(String[] args) throws IOException {
Scanner s = null;
try {
s = new Scanner(System.in);
int aNumbers[] = new int[s.nextInt()];
for (int i = 0; i < aNumbers.length; i++) {
aNumbers[i] = s.nextInt();
}
SplitIntArray p = new SplitIntArray(aNumbers);
p.write();
} finally {
if (s != null) {
s.close();
}
}
}
SplitIntArray(int[] numbers) {
this.bset = new BitSet();
this.aNumbers = numbers;
for (int i : numbers) {
this.sum += i;
}
int sumHalf = sum / 2;
this.aS = new int[sumHalf + 1];
aS[0] = 0;
Arrays.fill(aS, 1, aS.length, Integer.MAX_VALUE);
for (int i = 1; i <= numbers.length; i++)
for (int j = 0; j <= sumHalf - aNumbers[i - 1]; j++)
if (aS[j] < i && Integer.MAX_VALUE == aS[j + aNumbers[i - 1]]) {
aS[j + aNumbers[i - 1]] = i;
}
}
private void recoverNumbers(int i) {
if (aS[i] > 0) {
int idx = aS[i] - 1;
recoverNumbers(i - aNumbers[idx]);
System.out.println("1. " + aNumbers[idx] + " ");
bset.set(idx);
}
}
void write() {
for (int i = sum / 2; i >= 0; i--)
if (aS[i] != Integer.MAX_VALUE) {
System.out.println("Summen: " + i + " " + (sum-i));
recoverNumbers(i);
break;
}
System.out.print("2. ");
for (int i = 0; i < aNumbers.length; i++)
if (!bset.get(i)) {
System.out.print(aNumbers[i] + " ");
}
}
}
Oder ist das einfacher mit einem anderen Algorithmus (Backtracking oder so?) zu lösen? Muss nicht effizient sein, Hauptsache es funktioniert.
Vielen Dank schonmal.