Wie löst man diese Java-Aufgabe?

3 Antworten

daCypher
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
programmieren
27.07.2022, 13:21

Wenn ich dein Beispiel im Kopf durchgehe, komme ich auf diese Beste Route:

Tag 1: Stop 1 (25 Km)
Tag 2: Stops 2-6 (26 Km)
Tag 3: Rest (26 Km)

Der Dijkstra-Algorithmus hat damit eigentlich nichts zu tun. Der wäre eher dafür da, wenn man z.B. Querfeldein von Stop 1 zu Stop 6 laufen könnte und das dann nicht 26, sondern z.B. nur 20 Km wären.

Ich würde erstmal berechnen, wie weit die Strecken pro Tag im Durchschnitt sein müssten (insgesamt 77 km, durch 3 = 25,666 km) und dann für jeden Tag versuchen, möglichst nah an den Durchschnitt ranzukommen. Das wird bei einigen Sonderfällen (zwei sehr lange Abschnitte direkt hintereinander) zwar auch nicht 100%ig funktionieren, aber das wäre schon mal ein Anfang.

HakanBlue 
Fragesteller
 27.07.2022, 13:27

Ich habe mir auch schon gedacht, dass das eigentlich nichts mit dem Dijsktra-Algorithmus zutun hat.

Hättest du vielleicht einen Ansatz in Java, wie man dabei vorgeht (mit der /3 Rechnung und dann so nah wie möglich an der Zahl dran sein)?

Wäre echt hilfreich, weil ich bin ein Java-Noob.

0
daCypher  27.07.2022, 14:16
@HakanBlue 
import java.util.*;


public class Wanderer {
	public static void main(String[] args) {
		// Teilstrecken berechnen
		var sections = getSections(List.of(25,5,2,1,15,3,1,20,5), 3);


		// und ausgeben
		for (int tag = 1; tag <= sections.size(); tag++) {
			System.out.printf("Tag %d: %s (%d km)%n", tag, sections.get(tag-1), sections.get(tag-1).stream().mapToInt(Integer::intValue).sum());
		}
	}
	
	private static List<List<Integer>> getSections(List<Integer> distances, int sectionCount) {
		List<List<Integer>> result = new LinkedList<>();
		
		// Entfernungen in eine LinkedList packen, damit man einfach 
		// die Werte, die schon verarbeitet wurden, rausnehmen kann
		LinkedList<Integer> dist = new LinkedList<>(distances);
		
		// Tagesdurchschnitt berechnen
		double avgDistance = dist.stream().mapToInt(Integer::intValue).sum() / (double) sectionCount;
		
		// Listen für alle außer dem letzten Tag erzeugen und an das Ergebnis anfügen
		int currentStop = dist.pollFirst();
		for (int tag = 1; tag < sectionCount; tag++) {
			LinkedList<Integer> todayStops = new LinkedList<>();
			while (todayStops.stream().mapToInt(Integer::intValue).sum() + (currentStop / 2.0) < avgDistance) {
				todayStops.add(currentStop);
				currentStop = dist.pollFirst();
			}
			result.add(todayStops);
		}
		
		// alle verbliebenen Strecken als lezten Tag anfügen
		dist.push(currentStop);
		result.add(dist);
		
		return result;
	}
}
1
HakanBlue 
Fragesteller
 27.07.2022, 14:58
@daCypher

Vielen lieben Dank! Du hast mir echt weitergeholfen. Zwar hab ich die Aufgabe jetzt nicht ganz so optimal wie du gelöst, aber immerhin! :)

1
daCypher  27.07.2022, 15:05
@HakanBlue

Bitteschön, gerne 😊

Ist auch erstmal nur ein Beispiel. Es ist gut, wenn du daraus deine eigene Variante baust, weil du dann logischerweise viel mehr lernst, als wenn du meinen Code nur kopierst. Viele benutzen z.B. auch Schleifen anstatt Streams. Bei diesem Beispiel hätte es sich z.B. auch gelohnt, eine Funktion zu bauen, die die Summe aus einer List<Integer> bilden kann.

0
schnfz
27.07.2022, 13:15

Das ist keine „Java-Aufgabe“, sondern eine in algorithmischem Denken. Der Dijkstra wird dir dabei nicht direkt helfen, auch wenn er als Inspiration nützlich sein kann.

Mal es dir auf einem Blatt Papier auf und überleg dir, wie du ohne Computer vorgehen würdest. Oft hilft es, bewusst schlechte Lösungen anzusehen oder sich Sonderfälle anzusehen (was wäre, wenn die Abstände gleich wären, etwa jeden km einer? Was, wenn du die Strecke nur in 2 Teilstrecken zerlegen musst?)