Algorithmus suche/Problem

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Algorithmus suche/Problem

    Hallo,

    habe eine kleine Aufgabe bekommen, dabei sollen aus einer Textdatei Zahlenwerte(Preise) von fiktiven Produkten eingelesen werden. Dann soll die Summe von 2 Produkten gebildet werden, sollte die Summe den Endbetrag 0,65 , 0,98 oder 0,01 haben soll man die jeweiligen Zahlenpaare ausgeben. Und jedes Produkt darf nur zum bilden von 1. Paar benutzt werden.

    Beispiel: A = 1,60 B = 2,05 C = a+ b = 1,65 -> Paar (1,60 und 2,05) usw.

    Mein Problem ist jetzt, dass ich kein Verfahren/Algorithmus zum abbilden dieses finde.

    Hab schon in google gesucht und bin auf Backtracking aufmerksam geworden, aber wie ich das umsetzen soll ist mir ein Rätsel, da ja 1 Produkt nur einmal gepaart werden darf..

    VIelleicht stehe ich auch gerade auch etwas auf dem Schlauch, aber vielleicht kann mir ja einer von euch helfen.

    Gruß Chris

  • Hi,
    Backtracking würde vielleicht in Frage kommen, wenn die Endbeträge die Summen aus n Einzelbeträgen wären.
    Aber wenn das auf 2 reduziert ist, musst du nur jedes Produkt mit jedem Produkt testen.

    Quellcode

    1. length = produkte.length
    2. for i:=0 to length do
    3. for j:=i to length do #beginnen bei i+1, wenn 2x das selbe Produkt nicht erlaubt ist
    4. if produkte[i] + produkte[j] in (0.65, 0.98, 0.01)
    5. print produkte[i], produkte[j]
    6. j := j + 1
    7. j := i + 1


    n * log n, wenn ich mich nicht täusche

  • Chris2k schrieb:

    Warum zählst du i und j immer um einen hoch und addierst die dann?

    Das war offensichtlich mein Fehler ;) Hab i+j durch produkte[i ] + produkte[j] ersetzt, damit sollte es klarer werden.

    length in Pseudocodesprache? keine Ahnung. Kannst es auch einfach "n" nennen.
    Für "validen" Pseudocode wirst du auch die IN Abfrage durch eine weitere for-Schleife ersetzen müssen. Aber die ist ja relativ zur Produktmenge konstant, also irrelevant.

  • Also ein wenig klarer ist es schon geworden, nur jetzt versteh ich die Bedingungen bei den beiden For-Schleifen nicht mehr.

    Aber wenn ich das jetzt richtig verstanden habe, muss ich jede Zahl mit jeder anderen addieren und dann schauen, wass welches Produkt ergibt. Soweit ja klar, was mach ich mit den doppelten? MIt Hand hab ich das so gelöst, dass ich die nach dem sie ein Paar sind rauskicke und dann nicht mehr weiter benutze.

    Allerdings muss ich auch sagen, dass mir die Lösung ziemlich einfach vorkommt, wenn nicht sogar zu einfach, da muss es doch noch was anderes geben.

  • jedes Produkt darf nur zum bilden von 1. Paar benutzt werden.

    Das hatte ich irgendwie außen vor gelassen.

    Dann führe noch ein Array ein, in dem du dir merkst, was schon genutzt wurde.
    Du musst nur prüfen ob der J-Zähler im benutzt-Array vorhanden ist. Und die innere Schleife beginnst du bei i+1.

    Funktionieren sollte der Algorithmus. Nur bin ich oft überrascht was für geniale Wege es gibt. Vielleicht gibts ja noch was besseres als n * log n

    Quellcode

    1. benutzt = []
    2. length = produkte.length
    4. for i:=0 to length do
    5. for j:=i + 1 to length do
    6. if j not in benutzt AND produkte[i] + produkte[j] in (0.65, 0.98, 0.01)
    7. benutzt[] = i
    8. benutzt[] = j
    9. print produkte[i], produkte[j]
    10. j := j + 1
    11. j := i + 1
    Alles anzeigen

  • Super, danke!

    vielleicht kann mir einer von euch nochmal unter die Arme greifen und zwar versuche ich mein Algorithmusproblem zu implementieren.
    Problem dabei ist, ich komm ja zu Ergebnissen, aber diese sind nicht optimal, da ich ja jede Zahl nur einmal verwenden soll und die maximale Anzahl rauskommen soll, deswegen möchte ich im Fall, dass er ein neues Paar findet das alte Tauschen.
    d.h so viel, dass ich die 2te Zahl der addition austauschen möchte. Mein Problem sieht wie folgt aus: Das kann ja jetzt an jeder Stelle auftauchen und somit kann ich mir die Zahlen ja nicht in Variablen schreiben, da ja diese überschrieben werden. Meine Frage: Wie finde ich jetzt zu der passenden ersten Ziffer in der Liste den passenden 2ten Teil, der ersetzt werden soll? Oder sollte ich das doch anders lösen, vielleicht mit einer verkettetn Liste? Wobei ich dabei keinen Plan habe wie so eine zu realisieren ist, sondern mir nur über das Prinzip der Funkton im Klaren bin!
    Ich hoffe, dass meine Ansätze nicht zu großer Müll sind.

  • Okay, hab mittlerweile mal herausgefunden das das doch nicht so einfach geht wie ich mir das gedacht hatte mit der Arrayliste, deswegen halte ich eine verkettet Liste für sinnvoller. Was meinen die Experten?
    Habe mir schon soweit eine Liste geschrieben mit den Methoden zum einfuegen, ausgeben.
    Jetzt muss ich nur noch rausbekommen wie ich das mache, dass ich genau das Element aus der Liste heraushole, dass raus soll.
    Annahme:

    Ich habe in der Liste hintereinander zwei Zahlen stehen, diese Bilden ein Paar. Das erste wäre 10.33 und das zweite 2.22. Danach folgt das nächste Paar mit anderen Werten usw. Nun habe ich 3.22 und das Bildet mit 10.33 auch ein Paar, also die 2.22 soll druch 3.22 ersetzt werden.
    Wie kann ich das lösen, dass genau das Element irgendwo in der Liste ersetzt werden soll?
    Das ist noch mein einziger Haken. Ich hoffe das ist verständlich, ansonsten fertige ich morgen mal eine kleine "Skizze" an.

  • Nicht in der Geschwindigkeit, die ist mir ziemlich egal. Es geht mir darum das optimum an Pärchen zu finden, da ich durch die einfache Methode wenn ein Paar Gefunden schliesse die beiden Zahlen aus in den meisten Fällen nicht die optimale Anzahl an Paaren finde, denn wenn man die anders kombinieren würde unter Umständen mehr Paare finden würde.
    Skizze folgt später.

  • Chris2k schrieb:

    Es geht mir darum das optimum an Pärchen zu finden

    Das hast du aber bisher noch nicht erwähnt! Sowas funktioniert natürlich nicht mit einem Greedy Verfahren.

    Ich würde dir einfach empfehlen erst ein paar andere Backtracking Algorithmen zu verwenden, von denen es bereits Implementierungen und natürlich Dokumentation gibt. (z.B. Knapsack)
    Siehe hier: easy-coding.de/knapsack-problem-algorithmus-t2908.html

    Der Algorithmus wird dann so funktionieren, dass immer, wenn du ein Päärschen gefunden hast, das funktioniert,
    -> du einmal diesen Weg gehst
    -> und einmal den Weg gehst ohne das Päärschen zu verwenden

    Der Returnwert ist immer die Anzahl der Kombinationen. Fortgefahren wird, wenn dieser Returnwert nicht überschritten wird.

  • Ich musste auch spontan an das Knapsackproblem denken. Das es sich um ein klassisches NP-vollständiges-Problem handelt wissen wir, dass es nur durch (geschicktes) ausprobieren lösbar ist und man sich, wie bereits erwähnt, intensiv mit Backtracking zu beschäftigen muss.
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]

  • Irgendwie hänge ich jetzt bei der Implementierung total fest, die Theorie ist ja mehr als klar.
    Die bisherige Implementierung sieht wie folgt aus.

    Quellcode

    1. for ( a = 0; a < length; a++)
    2. {
    5. for ( b = a + 1; b < length; b++)
    6. {
    7. produkt = zahlen.get(a) + zahlen.get(b);
    8. komma_pruef = ( produkt * 100 ) % 100;
    9. if ( komma_pruef == 11 || komma_pruef == 33 || komma_pruef == 55 || komma_pruef == 77 || komma_pruef == 99)
    10. {
    12. if ( used.contains(zahlen.get(a)) || used.contains(zahlen.get(b)))
    13. {
    14. break;
    15. }
    16. else
    17. {
    18. used.add(zahlen.get(a));
    19. used.add(zahlen.get(b));
    20. count++;
    21. break;
    22. }
    23. }
    25. }
    27. }
    Alles anzeigen



    Ich habe eine Datei mit 200 Werten, da sollten im optimalen Fall 87 Pärchen entstehen, ich komm nur auf 75.
    Irgendwie komme ich nicht auf den Weg zurück,also wenn das mit einem Paar nicht hin haut, denn das oben ist ja quasi wieder nur der Weg wie ich die nicht optimale Anzahl bekomme.
    Denn ich nehme ja element a und gehe das mit allen elementen von b durch und schaue ob ich ein Paar gefunden habe, bei dem diese Zahlen noch nicht verwendet wurden.
    Kann mir vielleicht jemand einen Denkanstoss an den Weg zurück geben? Bin in meinen Wirrwar mehr als am verzweifeln.

  • Quellcode

    1. produkt = zahlen.get(a) + zahlen.get(b);

    Das ist übrigens eine Summe ;)

    Habe dein erstes Posting nochmal gelesen und es bleibt unklar.
    Was suchst du denn eigentlich? Summe oder Produkt? Und dürfen die verwendeten Zahlen nicht mehrmals vorkommen oder darf es die Summe nur einmal geben?

    Aber deinem Code feht auch so noch einiges. Das ist noch nichtmal der Algorithmus aus Posting 6... noch ganz ohne Backtracking.
    Backtracking bedeutet in den seltensten Fällen "runterschreiben"... befass dich also besser nochmal damit...

    Mit Garantie, dass es nicht funktionieren wird, habe ich dir mal folgendes Snippet als Beispiel gebaut. Halt dich nicht daran!

    Quellcode

    1. if(Loesungen.contains(gesuchteSummen)) {
    2. ArrayList<Double> copy = (ArrayList<Double>) Paare.clone();
    3. copy.remove(i);
    4. copy.remove(j);
    6. if(backtrack(copy) > backtrack(Paare)) {
    7. System.out.println(Paare.get(i)+"+"+Paare.get(j));
    8. Paare = copy;
    9. }
    10. }

  • Sorry...
    Bin momentan etwas durcheinander.
    Also ich Suche die Summe 2er Zahlen.
    Jede Zahl darf nur einmal zur Bildung eines Päärchens verwendet werden.
    Also hat man z.b die Zahlen a-d darf man nur ein mal a nutzen und jedes andere Elemenet auch nur einmal, in welcher Kombination ist egal. Die Summe die rauskommt ist relativ egal, da es ja um die Nachkommastellen geht. WIchtig ist halt, dass jede vorkommende Zahl nur einmal verwendet werden darf.

    Ist es nicht möglich, dass ich z.B. A + B = ? A + C = ? So lange durchgehe, bis A mit irgendwas ein Paar gibt, dann A und B wegschreiben, dass diese nicht mehr genutzt werden dürfen und mit Element B + ... weitermache und hinterher dann schaue, welches die größte Anzahl an Paaren liefert?

  • Ok, alles klar, dann waren wir ja richtig.
    Was du sagst ist richtig. Also einmal A+B verwenden. Einmal auf A+B verzichten und weitersuchen.
    Aber mit 2 For-Schleifen geht das nunmal nicht. Die Entscheidung ob du etwas verwendest oder lieber weitersuchst, kommt nicht nur einmal.

    Wenn ich dir die Lösung in 5 Minuten runterschreiben könnte, würd ich das machen.. aber das erfordert mehr Gehirnschmalz ;)