Java: Integer stapelweise

Question

Java: Integer stapelweise

8

Ich habe mich gefragt, was der beste Weg ist, eine bestimmte Menge von Zahlen in Bezug auf die Verarbeitungszeit zu verarbeiten. Nimm Gegenstände mit: 9, 18, 7, 8, 4, 9, 11, 15, 3, 8, (Punkt 1 hat eine Bearbeitungszeit von 9, Punkt 2 hat eine Bearbeitungszeit von 18 usw.)

Wenn das Zeitlimit für die Stapelverarbeitung auf 20 eingestellt ist, wäre eine mögliche Gruppierung der Artikel in Stapel: {1, 3, 5} {2} {4, 6} {8, 9} {7, 10} (Gruppe 1 ist 9 + 7 + 4 = 20) usw., also 5 Stapel von Artikeln gemacht, wo der Inhalt ist & lt; = 20.

Idealerweise möchte ich, dass sie so wenig Gruppen wie möglich einsortiert werden. Der obige Fall besteht aus mindestens 5 Gruppen mit einem Inhaltslimit von 20 ...

Danke

java integer batching

binary101 28.11.2012, 19:57

quelle

2 Antworten

3

Nimm das größte aus dem IN-Set und setze ein neues Set S. (Punkt 2, Wert 18)
Versuchen Sie, das größte Element mit dem Wert & lt; = (20 - 18) zu finden: none, fügen Sie S zu einer Liste von Mengen hinzu.
wenn IN nicht leer ist GOTO 1

Iterationen:

%Vor%

Der Code:

%Vor%

Das Ergebnis:

%Vor%

Aubin 28.11.2012 20:14

quelle

Tags und Links java integer batching

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Wie wird md5Hash für com.google.appengine.api.blobstore.BlobInfo berechnet?

score 4 · Accepted Answer

Wenn das Zeitlimit für die Stapelverarbeitung auf 20 gesetzt ist, ...

Ich nehme also an, dass es kein Element gibt, das größer ist als Stapelverarbeitungszeitlimit . Hier ist mein Ansatz:

Sortieren Sie zuerst die Artikel. Dann bekommen Sie 2 Zeiger für die Liste, eine ist bei index 0 ( linker Zeiger ) und der andere am letzten Index ( right-pointer ).
Nimm das Element des rechten Zeigers und füge es zu einer Unterliste hinzu. Nehmen Sie die Element des linken Zeigers und fügen Sie es der gleichen Unterliste hinzu. Wenn die Summe von Die Elemente in der Unterliste sind kleiner als limit, linker Zeiger aktualisieren (set es zum nächsten Element) und versuche, es hinzuzufügen. Setzen Sie diesen Vorgang fort, bis a Unterliste ist gefüllt.
Beginnen Sie dann mit dem Füllen der nächsten Unterliste. Verbrauchen Sie alle Elemente konstruiere Unterlisten.

Implementierung in Java:

%Vor%

Drucken der Gruppen:

%Vor%

Ausgabe: (Jede Zeile bezeichnet eine Gruppe von Zahlen)

%Vor%