Maximale KM-Kosten

[El Hadji]

Servus Community,
Ich hätte mal wieder eine Frage zu einer Aufgabe.
Die erste Methode getTeilroute müsste so stimmen wie ich es programmiert habe.
Aber zur Methode getMaxKmKosten, habe ich nicht wirklich eine Idee. Eventuell die kmKosten auf Double_MAX.VALUE setzen und dann die liste durchlaufen und immer die Kosten um 1 verringern? Habt ihr eine Idee für mich?

Hier mein Code:

import java.util.*;

public class Routenoptimierung
{
   private ArrayList<Strecke> liste;
  
    public Routenoptimierung()
    {
        liste = new ArrayList<Strecke>();
       
    }

  
    public Strecke [] getTeilroute(Strecke [] route, double kmKosten)
    {
        for (int i = 0; i < route.length; i++)
        {
            double gewinn = route[i].getWert()-(route[i].getLaenge()*kmKosten);
            if( gewinn > 0)
            {
                liste.add(route[i]);
            }
        }
       
        Strecke [] teilroute = new Strecke [liste.size()];
        Iterator <Strecke> it = liste.iterator();
        for (int i = 0; it.hasNext(); i++)
        {
            teilroute[i] = it.next();
        }
       
        return teilroute;
    }
}

Ich wär euch echt dankbar.
mfg

 

[mihe7]

Die erste Methode getTeilroute müsste so stimmen wie ich es programmiert habe.

Nein. Du sollst nicht beliebige Elemente, deren Gewinn > 0 ist, zu einer Route zusammenfügen sondern die zusammenhängende Teilroute mit dem größten Gewinn auswählen - Nachtrag: sofern es eine solche überhaupt gibt...

Damit erübrigt sich erst mal Deine Frage zu getMaxKmKosten 🙂

 

[El Hadji]

Wieder mal Danke für die schnell Antwort.
Aber leider stehe ich auch wieder am Schlauch, ich kann nur den Gesamtgewinn oder sagen wir gesamtVerlust berechnen^^

  double gesamtgewinn = 0;
        for (int i = 0; i < route.length; i++)
        {
            gesamtgewinn += route[i].getWert()-(route[i].getLaenge()*kmKosten);
        }

Ich wäre über neue Ansatzvorschläge echt dankbar. Hab grad 1 Stunde herumprobiert -.-

 

[El Hadji]

Wieder mal Danke für die schnell Antwort.
Aber leider stehe ich auch wieder am Schlauch, ich kann nur den Gesamtgewinn oder sagen wir gesamtVerlust berechnen^^

  double gesamtgewinn = 0;
        for (int i = 0; i < route.length; i++)
        {
            gesamtgewinn += route[i].getWert()-(route[i].getLaenge()*kmKosten);
        }

Ich wäre über neue Ansatzvorschläge echt dankbar. Hab grad 1 Stunde herumprobiert -.-

ok bzw. so

 double besteMenge = Double.MAX_VALUE;
        for (int i = 0; i < route.length-1; i++)
        {
            double teilmenge = route[i].getWert()-(route[i].getLaenge()*kmKosten);
           
            for (int j = i+1; j < route.length; j++)
            {
                teilmenge += route[j].getWert()-(route[j].getLaenge()*kmKosten);
               
            }
           
            if(teilmenge < besteMenge)
            {
                besteMenge = teilmenge;
            }
      
        }

Dadurch hätte ich zusammenhängende Teilmengen überprüft. Nur leider hab ich keinen Schimmer wie ich die einzelnen Strecken speichern sollte

 

[mihe7]

Du sollst nicht wild herumprobieren, sondern ein Problem lösen.

Nimm mal ein Blatt Papier (das ist dieses Cellulose-Zeug, auf das sich mit einem geeigneten Schreibgerät Farbe aufbringen lässt), und mal Dir mal eine Route mit sagen wir mal sechs Strecken auf.

Die Strecken verbindest Du dabei entlang der Route mit Linien und nummerierst sie, beginnend bei 0, durch. Die erste Strecke hat die 0, die zweite die 1 usw.

Eine zusammenhängende Teilstrecke ist damit durch Angabe von zwei Strecken eindeutig festgelegt: z. B. erste Teil der Teilstrecke ist Strecke Nr. 2, letzter Teil der Teilstrecke ist Strecke Nr. 4.

Jetzt überleg Dir einfach mal, wie Du die beste Teilstrecke finden kannst - ohne Computer.

 

[El Hadji]

Jo probiert, zu mehr Erkenntnis komm ich auch nicht:

 

[mihe7]

Nicht konkrete Werte nehmen. Wenn Du zwei beliebige Teilstrecken als Start und Ziel nimmst, wie hoch ist dann der Gewinn - ganz allgemein beschrieben? Gesucht sind jetzt Start und Ziel, so dass Gewinn maximal wird... Wie funktioniert das? Wenn ich noch mehr schreibe, dann kann ich gleich die Lösung posten.

 

[El Hadji]

Naja die Summe der Gewinne von Start bis Ziel.

 

[El Hadji]

das Problem nennt sich ja Largest SubArraySum oder?

 

[mihe7]

das Problem nennt sich ja Largest SubArraySum oder?

Ja. Das spielt aber keine Rolle. Für die Aufgabe sollte ein naiver Algorithmus reichen und den zu finden, solltest Du schon in der Lage sein.

Naja die Summe der Gewinne von Start bis Ziel.

Genau. Wenn Du jetzt eine Start-Strecke gegeben hättest, wie könntest Du dann die optimale Teilroute finden?

 

[El Hadji]

So ich hab mich nochmal dran gewagt. was hält ihr von meiner optimalen Teilroute?
Ist der Ansatz dieses Mal richtig?

          ArrayList<Strecke> teilroute = new ArrayList<Strecke>();
          double maxGewinn =0;
          double streckenGewinn = 0;
          int start = 0;
          int ende = 0;
          for (int i = 0; i < route.length-1; i++)
          {
              double streckengewinn = 0;
              int count = 0;
              for(int j = route.length-1; j >= i; j--)
              {
                  streckengewinn += (route[j].getWert()-kmKosten*route[j].getLaenge());
                  count++;
               }
              
               if(streckengewinn > maxGewinn)
               {
                   maxGewinn = streckengewinn;
                   start=i;
                   ende=i+count;
                }
            }
          
            for (int i = start; i <ende; i++)
            {
                teilroute.add(route[i]);
            }
           
            Strecke [] fertig = new Strecke [teilroute.size()];
            Iterator<Strecke> it = teilroute.iterator();
            for (int i = 0; it.hasNext(); i++)
            {
                fertig[i] = it.next();
            }
           
            return fertig;
      
       
       
      
       
       
    }
}

 

[mihe7]

Nö. Jetzt gehst Du davon aus, dass die Teilroute immer auch die letzte Strecke enthalten muss.

 

[El Hadji]

Wieso immer die letzte strecke, deswegen springe ich ja von hinten nach vorne durch.

 

[mihe7]

deswegen springe ich ja von hinten nach vorne durch.

Ob Du von vorne oder von hinten "durchspringst" spielt keine Rolle: du summierst einfach die Streckengewinne auf.

Hier:

              double streckengewinn = 0;
              int count = 0;
              for(int j = route.length-1; j >= i; j--)
              {
                  streckengewinn += (route[j].getWert()-kmKosten*route[j].getLaenge());
                  count++;
               }

Du berechnest damit die Summe der "Streckengewinne" aller Teilstrecken zwischen route[i] und route[route.length-1]. Die Reihenfolge der j hat darauf keinen Einfluss.

 

[El Hadji]

Du berechnest damit die Summe der "Streckengewinne" aller Teilstrecken zwischen route[i] und route[route.length-1]. Die Reihenfolge der j hat darauf keinen Einfluss.

Genau und die maximale Streckengewinne müssen doch auch automatisch die optimale Teilroute sein

 

[mihe7]

Nein. Nimm z. B. mal folgende Streckengewinne an: 1,1,1,-10,-10...

 

[El Hadji]

Ok ich glaub jetzt hab ichs gecheckt!

  ArrayList<Strecke> teilroute = new ArrayList<Strecke>();
          double maxGewinn =0;
          double streckenGewinn = 0;
          int start = 0;
          int ende = 0;
          for (int i = 0; i < route.length; i++)
          {
              double streckengewinn = 0;
              int count = 0;
              for(int j = i; j < route.length; j++)
              {
                  streckengewinn += (route[j].getWert()-kmKosten*route[j].getLaenge());
                  count++;
                 
                  if(streckengewinn > maxGewinn)
               {
                   maxGewinn = streckengewinn;
                   start=i;
                   ende=i+count;
                }
               }
              
            }
          
            for (int i = start; i <ende; i++)
            {
                teilroute.add(route[i]);
            }
           
            Strecke [] fertig = new Strecke [teilroute.size()];
            Iterator<Strecke> it = teilroute.iterator();
            for (int i = 0; it.hasNext(); i++)
            {
                fertig[i] = it.next();
            }
           
            return fertig;
      
       
       
      
       
       
    }
}

 

[mihe7]

Ok ich glaub jetzt hab ichs gecheckt!

🙂

Nach der for-Schleife lässt sich aber noch ein wenig optimieren... Die teilroute brauchst du gar nicht, du kannst direkt in das fertig-Array schreiben.

 

[El Hadji]

jo hast recht, aber ich wollt nur zeigen dass ich die Problematik verstanden hab.

Aber bei Frage 2 also maximale KM Kosten berechnen, kann ich mir nicht vorstellen was gemeint ist.

 

[El Hadji]

Aja 1 noch, vielen vielen Dank für dein Bemühen und deine Hilfe!!

 

[mihe7]

Aber bei Frage 2 also maximale KM Kosten berechnen, kann ich mir nicht vorstellen was gemeint ist.

Sei r eine Route. Gesucht ist das maximale x mit getTeilroute(r,x)=r.