Zahlen verteilen

[Jack1995]

Ich habe eine Frage: nehmen wir an ich hab beliebig viele zahlen mit unterschiedlichen Werten. Wie kann ich diese Zahlen nun auf zwei Seiten verteilen,sodass der Unterschied der Summe der einzelnen Seiten jeweils so minimal wie möglich ist?

 

[nevermind 10844]

Ich denke du musst genauer werden um das Problem überschaubar zu machen.
Müssen es z.B. gleich viele Zahlen auf jeder Seite sein? Muss das Ergebnis optimal sein oder reicht eine Annäherung? Falls Annäherung ausreichend, wie groß darf die Tolleranz sein? ...

Für eine schnelle Lösung könnte vllt. Folgendes funktionieren.
Du nimmst die jeweils größte oder kleinste Zahl und packst diese auf die eine Seite und danach machste dasselbe mit der anderen Seite und das ständig im wechsel.
Sollte für eine erste Lösung ein akzeptables Ergebnis ergeben.

Um das Ergebnis zu optimieren könntest du jetzt die Differenz berechnen und schauen durch den Tausch welcher Werte diese Differenz bestmöglich ausgeglichen wird.

Nur mal so ein schneller Gedanke.

 

[Gast2]

Du kannst die Zahlen sortieren und dann auf die beiden Listen verteilen:

	public static void main(String[] args) {
		List<Integer> numbers = generateNumbers(50, 100);
		List<Integer> list1 = new ArrayList<>();
		List<Integer> list2 = new ArrayList<>();
		
		spread(numbers, list1, list2);
		
		System.out.printf("Liste 1: %s Zahlen und Summe %s\n", list1.size(), sum (list1));
		System.out.printf("Liste 2: %s Zahlen und Summe %s", list2.size(), sum (list2));
	}

	public static List<Integer> generateNumbers(int max, int quantity) {
		List<Integer> numbers = new ArrayList<>();
		
		Random rand = new Random ();
		for (int i = 0; i < quantity; i++) {
			numbers.add (rand.nextInt(max));
		}
		
		return numbers;
	}
	
	public static void spread (List<Integer> numbers, List<Integer> list1, List<Integer> list2) {
		// sortieren
		Collections.sort(numbers, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				if (o1 == o2) {
					return 0;
				}
				return o1 < o2 ? 1 : -1;
			}
		});
		
		// auf listen verteilen
		int sum1 = 0;
		int sum2 = 0;
		for (int number : numbers) {
			if (sum1 < sum2) {
				list1.add (number);
				sum1 += number;
			} else {
				list2.add (number);
				sum2 += number;
			}
		}
	}
	
	public static int sum (List<Integer> numbers) {
		int sum = 0;
		for (int i : numbers) {
			sum += i;
		}
		return sum;
	}

 

[Jack1995]

Also um genauer zu werden: ich hab mehrer Objekte, die jeweils ein Atribut Zahl enthalten und ein Attribut Geld, ich muss jetzt beliebig viele Objekte so auf 2 Seiten verteilen, dass der Unterschied der Summe der Zahlen möglichst gering ist, jedoch die summe des Geldes zwischen beiden Seiten darf nicht größer als 5000 sein, also max. 5000 unterschied vom Geldwert her.

 

[Marco13]

Was mir Sortieren (also irgendeine Ausprägung einer "Greedy-Strategie") ist wohl recht einfach, aber ... ingesamt fühlt sich das im Moment an, als könnte das mit Partition problem - Wikipedia, the free encyclopedia zu tun haben und das finden DER optimalen Lösung entsprechend schwierig sein (hab aber nicht wirklich drüber nachgedacht, nur ein erster Gedanke)

EDIT: Nach einem zweiten Blick auf den Wiki-Artikel: Ja, das könnte schon SEHR nah dran sein Da ist aber auch was zu Approximationen (mit Sortierung) geschrieben....

 

[Landei]

Wenn die Summe aller Zahlen N ist, könnte man es als Rucksackproblem für N/2 mit Wert = Gewicht modellieren.

 

[hüteüberhüte]

Vielleicht auch wieder ein Backtracking-Problem: Verteile die Zahlen solange auf die zwei Hälften, bis 5000 überschritten ist oder die Differenz der Summen der Zahlen möglichst gering ist. "Möglichst gering" ist natürlich nicht wirklich ein Abbruchkriterium. Man müsste dann die kleinste berechnete Differenz merken/speichern. Aber der Greedy-Ansatz klingt doch erst mal gut.

 

[D4rkscr43m]

Also meiner Meinung nach sollte ich die geringste Differenz bekommen, wenn ich:
1. Sortiere (größte zuerst)
2. das erste (größte) Objekt nehme und auf Stabel A lege
3. so lange Objekte auf Stapel B lege bis Summe(Stapel B) >= Summe(Stapel A)
4. so lange Objekte auf Stapel A lege bis Summe(Stapel A) >= Summe(Stapel B)
5. wenn noch Elemente vorhanden sind wieder zu 3. Springen.

in Java könnte das dann so aussehen:

static List<Integer> zahlen = Arrays.asList(2, 500,2300,54,2334, 4000,20,9);
static List<Integer> stapelA = new ArrayList<Integer>();
static List<Integer> stapelB = new ArrayList<Integer>();

public static void main(String[] args) throws Exception {

	Integer[] z = zahlen.toArray(new Integer[0]);
	List<Integer> zu = stapelA;
	List<Integer> nichtzu = stapelB;
	Arrays.sort(z, new Comparator<Integer>() {
		public int compare(Integer o1, Integer o2) {
			return o2 - o1;
		}
	});
	for(int i = 0; i < z.length; i++) {
		if(sum(zu) > sum(nichtzu)) {
			List<Integer> b = zu;
			zu = nichtzu;
			nichtzu = b;
		}
		zu.add(z[i]);
	}
	System.out.println(sum(stapelA));
	System.out.println(sum(stapelB));
}

static int sum(List<Integer> stapel) {
	int summe = 0;
	for (Integer integer : stapel) {
		summe += integer;
	}
	return summe;
}

Auch wenn ich da zufällige Startwerte reinhämmer komme ich auf keine sonderlich großen Abweichungen. Sollte allerdings ein Wert der Startmenge von über 50 % der gesammtsumme ausmachen und größer sein als 5000 kommst du ja um eine Differenz von über 5000 nicht drum herum

 

[hüteüberhüte]

Nein, berechnet nicht die optimale Lösung. Nicht mal annähernd: Sei 1,1,1,1,4 gegeben. Dann würden sich die Zahlen so verteilen:

zu : nichtzu
1    1
1    1
4

Poste gleich mal Ansatz mit Backtracking, kann aber noch dauern

 

[D4rkscr43m]

@hüteüberhüte: doch funktioniert problemlos, deswegen sortier ich ja extra absteigend

 

[Niggel595]

Nur zur Info... Da will sich jemand nur wieder eine einfache Lösung für die 2. Aufgabe des diesjährigen BUNDESWETTBEWERB INFORMATIK erschleichen...

Bundeswettbewerb Informatik: 1. Runde

 

[hüteüberhüte]

@hüteüberhüte: doch funktioniert problemlos, deswegen sortier ich ja extra absteigend

Stimmt, daran hatte ich jetzt nicht gedacht. Aber sobald ein zweiter Wert hinzukommt (z.B. Zahl u. Gewicht), funktioniert der Greedy net mehr. Aber wenn es hier nur um die Lösung zu einen Wettbewerb geht, poste ich auch nix.

Bt hätte so ausgesehen: Array über EingabeLänge erstellen: Bei 0 in Liste A einfügen, bei 1 aus Liste A in B einfügen und bei 2 aus B nehmen und wieder auf 0 setzen. Summe u. noch zu verteilende Werte kann man sich merken/speichern. Hth. Weiteres poste ich net dazu. Greetz.

Gesendet mit Tapatalk 2

 

[Marco13]

1. Sortiere (größte zuerst)
2. das erste (größte) Objekt nehme und auf Stabel A lege
3. so lange Objekte auf Stapel B lege bis Summe(Stapel B) >= Summe(Stapel A)
4. so lange Objekte auf Stapel A lege bis Summe(Stapel A) >= Summe(Stapel B)
5. wenn noch Elemente vorhanden sind wieder zu 3. Springen.

Bei solchen Greedy-Ansätzen ist es manchmal ein bißchen fummelig, aber i.a. nicht "schwer", ein Gegenbespiel zu finden. Im speziellen ist bei Partition problem - Wikipedia, the free encyclopedia genau dafür ein Gegenbeispiel beschrieben.

 

[D4rkscr43m]

@Marco13, hast du vielleicht noch ein paar Gegenbeispiele? Dieses eine kann man ja noch relativ einfach "umgehen".

[EDIT]So ich hab ne "Lösung" dir zumindest für von mir ausgedachte "Problemfälle" funktioniert.

Wer noch Zahlenreihen zum Testen hat, nur her damit [/EDIT]

 

[hasso]

Kann man nicht einfach den Greedy nehmen, so wie er ist und nachdem die zwei Listen erstellt wurden berechnet man deren Summen. Sind die Summen gleich oder nur ein Zähler auseinander passt alles, sind sie weiter auseinander ziehe ich sie voneinander ab.

Die Differenz teile ich durch zwei, das ist dann der Wert der nachkorrigiert werden muss. Und dann muss ich doch nur noch je eine Zahl aus beiden Listen finden die diesen Wert als Differenz haben und diese tausche ich dann. Sollte es ein solchens Paar nicht geben dürfte eigentlich keine Verbesserung mehr möglich sein.

 

[Marco13]

@Marco13, hast du vielleicht noch ein paar Gegenbeispiele? Dieses eine kann man ja noch relativ einfach "umgehen".

Ohne die Details wirklich nachvollzogen zu haben: Soweit ich das überflogen(!) habe, ist das zu lösende Problem NP-vollständig. Es ist einfach, eine Implementierung zu finden, die die optimale Lösung liefert, aber dieses Implementierung wird keine Polynomiale Laufzeit mehr haben. Wenn du behaupten willst, eine Implementierung gefunden zu haben, die für ein NP-vollständiges Problem in polynomialer Zeit die optimale Lösung findet: PM an mich, bitte

 

[D4rkscr43m]

Marco, geb mir mal bitte ne Definition die ich konkret nachvollziehen kann, dann prüfe ich das gerne gegen ^^ ich hab nämlich so ziemlich 0 Ahnung von polynomialer Zeit

 

[hüteüberhüte]

@Marco13: Es wird allgemein angenommen, dass NP-vollst. Probleme nicht in Polynomialzeit lösbar sind. Wer sich trotzdem auf die Suche nach einer Lösung macht, ist entweder ein Genie oder ein Idiot. Und weil ich nicht annehmen, dass hier Genies sind, tippe ich mal auf Letzteres. Außerdem, warum sollte man gerade dir die Lorbeeren der Arbeit geben, wenn wirklich jemand einen schnelleren Algorithmus gefunden hätte ^^

B2t: Da es sich hier um Bundeswettbewerb Informatik handelt, sollte nicht weiter über Lösungen diskutiert werden, imho

 

[Marco13]

@D4rkscr43m: Eine einfache Definition ist: Das ist die Sorte von Problemen, für die allgemein angenommen wird, dass es keine effiziente Lösung gibt (also keinen Algorithmus, der auch bei "großen" Aufgaben in "vertretbarer" Zeit IMMER DIE optimale Lösung findet).

Außerdem, warum sollte man gerade dir die Lorbeeren der Arbeit geben, wenn wirklich jemand einen schnelleren Algorithmus gefunden hätte ^^

Weil ich ein paar Millionen Dollar gerade gut gebrauchen könnte