Greedy-Algorithmus

[Tina87]

Hallo,
habe Probleme meine Hausaufgabe zu lösen.
Erstmal zur Aufgabe:
Professor Midas fährt auf einer Autobahn von Newmark nach Reno. Mit vollem Tank fährt sein Auto genau n Kilometer weit. Zu Beginn der Reise ist sein Auto vollgetankt. Midas möchte so wenige Tankstopps wie möglich machen.
Der Greedy-Algorithmus in eine Java-Methode implementiert werden:
int [] tankstopps (int n, int [] tankstellen, int z), wobei n die Reichweite des Autos ist und im Array tankstellen die Entfernungen der Tankstellen vom Startpunkt angegeben sind (tankstellen == {34,71,90}), z ist die Gesamtstrecke.
Die Methode soll ein Array mit den Nummern der Tankstellen zurückgeben(z.B. {0,2}= 1.und 3. Tabkstelle).

Da es ja Ziel ist, so wenige Stopps wie möglich zu machen, dachte ich, dass ich von hinten anfang zu überprüfen, ob ein Stop an dieser Tankstelle möglich ist.
Problem ist, dass wenn er an einer Tankstelle getankt hat, die Reichweite n neu zu benutzen.
Ach irgendwie schwierig zu erklären;-)
Hier mein bisheriger Lösungsansatz:

public class Greedy_Algorithmus
{
    public static void main (String [] args) {
        int n = 50;
        int [] tankstellen = {34,71,90};
        int z= 100;
        tankstopps (50, new int[]{34, 71, 90}, 100 );
    }
    static int [] tankstopps (int n, int [] tankstellen, int z) {
        int [] stopps;
        if (n >= z){
            return 0;
        }
        else {
            for (int i= tankstellen.length-1; i>=0; i--) {
                if (tankstellen[i] > n){
                    
                    ....

                }
            }
        }
    }
    return stopps;
}

Wäre nett, wenn mir jemand hilft!

 

[KrokoDiehl]

Habt ihr irgendwie Vorgaben das iterativ oder rekursiv zu lösen?

Jedenfalls ist das Vorgehen doch so:
- Solange du noch nicht am Ziel (z > 0) bist und die Reststrecke nicht in deiner Reichweite liegt (z > n)
- fahre zur letzten Tankstelle, die in deiner Reichweite liegt und tanke dort voll
- setze deine Reichweite zurück
- aktualisiere die Reststrecke und die Abstände zu den Tankstellen

Für mich klingt das spontan zumindest nach Rekursion, da man die Strecken immer wieder aktualisieren muss, was mir in der Rekursion leichter erscheint.

 

[Gast2]

Iterativ geht es auch relativ einfach - allerdings würde ich hier eigentlich auch das ganze eher rekursiv lösen

        else {
            boolean angekommen = false;
            int gefahren = 0;
            while(!angekommen){
            int bestTankstelle = 0;
            for (int i = 0; i < tankstellen.length; i++) {
                if (tankstellen[i] < n + gefahren){
                   if(tankstellen[i] > bestTankstelle){
                      bestTankstelle = tankstellen[i];
                   }
                }
            }
            System.out.println("Stoppe bei "+bestTankstelle);
            gefahren = bestTankstelle;
            if(gefahren + n >= z ){
                System.out.println("Kein weiterer Stop nötig");
                angekommen = true;
               }
            }
        }

Mal so als Sketch für die Iterative Lösung - musst halt noch zusehn das du dir die Tankstellen Ids wegspeicherst um nachher zurückzugeben wo du gestopt hast...

 

[Tina87]

Also erstmal danke für eure schnelle Hilfe.
Also ich denke, dass wir es iterativ lösen sollen, weil wir mit Rekursion noch nicht sehr viel gemacht haben.
Die Lösung, die hier iterativ vorgeschlagen wurde, verwirrt mich irgendwie etwas und sie gibt leider auch keinen String mit den Positionen der Tankstopps zurück, sondern bei welchen Km getankt werden soll.
Also mir erscheint es sinnvoll eine for-Schleife zu benutzen, die von hinten anfängt, weil Greedy doch den größmöglichen Gewinn erreichen will. Also wird er doch zuerst die hinterste Tanke testen.
Problem bei mir ist, dass ich mit den ganzen i´s durcheinander komme.
Deshalb hier nochmal meine sicherlich falsche Version:

public class Test
{
   public static void main (String [] args) {
        int n = 50;
        int [] tankstellen = {34,71,90};
        int z= 100;
        tankstopps (50, new int[]{34, 71, 90}, 100 );
    }
     static int [] tankstopps (int n, int [] tankstellen, int z) {
        int [] stopps={0};
        if (n >= z){
            System.out.println("keine Stopps nötig");
        }
        else {
            for (int i=tankstellen.length-1; i<0;i--) {
                if (tankstellen[i] < n) {
                    stopps[i] = i; 
                    n=tankstellen[i]+n;
                }
            }
           
        }
    } 
    return stopps;
}

 

[Final_Striker]

Ne, du musst nicht hinten anfangen. Der Greedy-Algo will in dem Fall mit dem vorhandenen Benzin soweit wie möglich fahren.

Meine Lösung wäre:

       public static void main (String [] args) {
            int n = 50;
            int [] tankstellen = {34,50,55,71,80,90};
            int z= 100;
            int[] stopps = tankstopps (50, new int[]{5, 12, 34, 51, 71, 83, 90, 120}, 100 );
            
            System.out.println(Arrays.toString(stopps));
        }
         static int [] tankstopps (int n, int [] tankstellen, int z) {
            int [] stopps= new int[tankstellen.length];
            
            int t = 0;
            int rechweite = n;
            
            while(rechweite < z){ // solange Reichweite kleiner als Strecke ist
        	
              // fahre so lange bis Reichweite kleiner als die Position der aktuellen Tankstelle ist
               if(rechweite < tankstellen[t]){ 
        	   
                   stopps[t-1] = 1; // tanke an der letzten Tankstelle
                   rechweite = tankstellen[t-1] + n; // neue Reichweite ist Tankstelle-km + Tankgröße
        	       
               }
        
        	t++;
            }
            
            return stopps;
        }

 

[Tina87]

Muss leider nochmal weiter nerven.
Du wolltest ja jetzt das Array in einen String umwandeln, warum?
Außerdem bin ich noch nicht mit der Ausgabe zufrieden ;-)
Ich will doch die Ausgabe als Array, so dass die Position der Tankstellen angegeben wird.
Wenn man bei der 1. und 3. Tankstelle getankt hat, soll "stopps = {0,2}" sein.
Problematisch ist nur, dass ich bei einem Array ja die Länge vorher schon festlegen muss und hier ja nicht im voraus wissen kann, wieviele stopps es gibt.
So wie ich das jetzt implementiert habe, kommen bei der Ausgabe irgendwelche hieroglyphen raus;(

public class Test {

    public static void main (String [] args) {
        int n = 50;
        int [] tankstellen = {34,71,90};
        int z= 100;
        System.out.println(tankstopps(50, new int[]{5, 12, 34, 51, 71, 83, 90, 120},100));
    }
        static int [] tankstopps (int n, int [] tankstellen, int z) {
        int [] stopps= new int[tankstellen.length];
        int t = 0;
        int i = 0;
            
        while(n < z){ // solange Reichweite kleiner als Strecke ist
            
            // fahre so lange bis Reichweite kleiner als die Position der aktuellen Tankstelle ist
            if(n < tankstellen[t]){ 
                stopps[t-1] = t-1; // tanke an der letzten Tankstelle
                n = tankstellen[t-1] + n; // neue Reichweite ist Tankstelle-km + Tankgröße 
            }
            t++;
        }
        return stopps;
    }
}

 

[Final_Striker]

Ich hab es nur ausgegeben, damit man mal schnell sieht was raus kommt.

    public static void main(String[] args) {
	int n = 50;
	int[] tankstellen = { 5, 20, 34, 42, 55, 71, 83, 95, 120 };
	int z = 100;
	int[] stopps = tankstopps(50, tankstellen, 100);

	// System.out.println(Arrays.toString(stopps));

	System.out.print("Es wurde an den Tankstellen: ");
	for (int i = 0; i < stopps.length; i++) {
	    if (stopps[i] == 1) {
		   System.out.print(i + ", ");
	    }
	}
	System.out.print("getankt.");
    }

    static int[] tankstopps(int n, int[] tankstellen, int z) {

	int[] stopps = new int[tankstellen.length];
	int t = 0;
	int rechweite = n;

	while (rechweite < z) {

	    if (rechweite < tankstellen[t]) {
		
		rechweite = tankstellen[t - 1] + n;
		stopps[t - 1] = 1;
	    }
	    t++;
	}
	return stopps;
    }

Edit:

An den Stellen im Array wo eine 1 steht wurde getankt. ;-)

 

[Tina87]

Dankeschön