Wechselgeld 5 besten Kombinationen



  • @hustbaer sagte in Wechselgeld 5 besten Kombinationen:

    @Quiche-Lorraine sagte in Wechselgeld 5 besten Kombinationen:

    @hustbaer
    Funktioniert deine Lösung auch mit 99999,99€?

    In der Aufgabenstellung steht nämlich:

    Fange beim Anwender eine Summe 0,01 < X < 100.000,00 ab.

    (siehe https://www.c-plusplus.net/forum/topic/350274/wechselgeld-5-besten-kombinationen/1)

    Theoretisch: ja. Praktisch wird das wohl relativ lange dauern 🙂

    Das blöde dabei ist halt dass man selbst mit dem €500 Schein dazu > 200 Scheine braucht, und ein nur begrenzt schlauer Algorithmus der halt einfach alle Möglichkeiten 200 Scheine auszuwählen durchprobiert ... naja das dauert halt ein bisschen.

    Ich hab das grad mal bei mir getestet, es läuft ohne Probleme auch mit der Zahl für die Top 5. Wenn ich sage 1000 Lösungen ausgeben, kommt die Zeit langsam in sinnvoll messbare Bereiche von 1.x Sekunden. (Hab https://www.onlinegdb.com/online_c_compiler benutzt)

    Das liegt scheinbar daran, das ich doch nen ganzen Teil der Kombinationen gar nicht erst teste. Ich habe auch so einen "firstype", die höchste Münze die ich der Lösung noch hinzufüge im nächsten Rekursionsschritt, bei mir biggestCoin genannt. Damit habe ich ebenfalls ein Abbruchkriterium, wenn das Restgeld mit der restlichen Münzen nicht erreicht werden kann. Ohne kommt die gleiche Lösung raus, aber bei hohen Beträgen messbar langsamer. Siehe hier:

        if (missingMoney < 0)
        {
            return;
        }
        if (missingMoney > coinValue[biggestCoin] * missingCoins)
        {
            //even with all highest coins its not enough, this check is not necessary, but much quicker
            return;
        }
    

    Ich hab auch umgekehrt immer nur ein Münze pro Rekursionsschritt hinzugefügt, dafür alle Münztypen statt nur ein Münztyp in jeder möglichen Menge zu testen. Das ist aber glaube eher irrelevant für die Performance. Es ändert nur die Reihenfolge, es kann maximal den lower bound schnellen finden.

        for(int i = biggestCoin; i < coinCount; ++i)
        {
            // lets try coin i and do recursive call
            *nextRes = i;
            addCoin(found, nextRes + 1, missingMoney - coinValue[i], missingCoins - 1, i);
            if (*found >= maxOutput)
            {
                return;
            }
        }
    

    Ansonsten passiert bei mir auch nichts weiter. Würde das Thema aber auch weniger relevant einschätzen, weil man eh nicht zig mal mit riesigen Zahlen testen wird.


  • Mod

    @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    @SeppJ sagte in Wechselgeld 5 besten Kombinationen:

    Aber nicht alle möglichen Stückelungen gehorchen dieser Annahme.

    Ja, das meinte ich.

    Ich meinte aber was anderes: Was machst du, wenn die Stückelung dem bewiesenermaßen nicht genügt. Dann gilt schließlich nicht mehr diese Annahme zur Performanceoptimierung:

    @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    Für normale Scheinverteilungen kannst du einfach Greedy wegnehmen restbegtrag / schein[n] in einer simplen for loop.



  • @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    Ich hab auch umgekehrt immer nur ein Münze pro Rekursionsschritt hinzugefügt, dafür alle Münztypen statt nur ein Münztyp in jeder möglichen Menge zu testen. Das ist aber glaube eher irrelevant für die Performance. Es ändert nur die Reihenfolge, es kann maximal den lower bound schnellen finden.

    Produziert das nicht haufenweise Duplikate?

    Das liegt scheinbar daran, das ich doch nen ganzen Teil der Kombinationen gar nicht erst teste. Ich habe auch so einen "firstype", die höchste Münze die ich der Lösung noch hinzufüge im nächsten Rekursionsschritt, bei mir biggestCoin genannt. Damit habe ich ebenfalls ein Abbruchkriterium, wenn das Restgeld mit der restlichen Münzen nicht erreicht werden kann.

    Sowas in der Art hab ich mir auch überlegt, hatte mir aber gedacht dass es vermutlich kaum was bringen wird. Ich werd das mal bei mir noch einbauen und schauen was dann mit 99999,99 geht 🙂



  • @SeppJ sagte in Wechselgeld 5 besten Kombinationen:

    @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    @SeppJ sagte in Wechselgeld 5 besten Kombinationen:

    Aber nicht alle möglichen Stückelungen gehorchen dieser Annahme.

    Ja, das meinte ich.

    Ich meinte aber was anderes: Was machst du, wenn die Stückelung dem bewiesenermaßen nicht genügt. Dann gilt schließlich nicht mehr diese Annahme zur Performanceoptimierung:

    @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    Für normale Scheinverteilungen kannst du einfach Greedy wegnehmen restbegtrag / schein[n] in einer simplen for loop.

    Dann muss man dann alles durchprobieren, was man für die Top5 eh muss. Aber da das Array nicht zu den Eingabedaten gehört, kann man diese Entscheidung statisch treffen. Im Endeffekt ändert sich nur wie und wie gut man die kürzeste Lösung schätzen kann. Man kann auch einfach 0 nehmen auf Kosten der Performance oder Betrag / schein[0].

    @hustbaer: Es gibt keine Duplikate, weil jede erzeugte Kombination ein monoton fallendes Array ist (50/10 ist eine Lösung für 60, 20/20/20 auch, aber 10/50 nicht). Und das die Extra-Bedingung so effizient ist, hab ich auch erst rausgefunden als ich sie testweise bei hohem Betrag man auskommentier hatte.



  • @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    @hustbaer: Es gibt keine Duplikate, weil jede erzeugte Kombination ein monoton fallendes Array ist (50/10 ist eine Lösung für 60, 20/20/20 auch, aber 10/50 nicht).

    Danke, manchmal steh ich ein bisschen auf dem Schlauch 🙂



  • @hustbaer Dein note type values Array ist falsch herum aufgebaut, daher die schlechte Performance.

    Du hättest quasi von mir abschreiben können.



  • @TGGC Habs jetzt ausprobiert, nochmal danke für den Tip!
    Genau eine Zeile Änderung in meinem Code (zwei wenn man das geänderte Kommentar mitzählt)...

    		//if (max_sensible_this_type_count < 1)
    		//	return; // it wouldn't even make sense to add one single note -> we're done
    		if (max_sensible_this_type_count * my_value < remaining_amount)
    			return; // we can't reach the target using fewer notes than the worst solution -> we're done
    

    ...und schon läuft es wie Schmidts Katze - braucht damit auch für die geforderten €99999,99 "so gut wie nix". Selbst wenn ich damit die besten 1000 Lösungen für €99999,99 berechne braucht die eigentliche Berechnung (=ohne printf) nur ~6 ms.

    Ich finde auch bei dir ist nicht etwa das Ausrechnen der Lösung kompliziert sondern nur das selbstgemachte abspeichern und rumschieben.

    Ich hatte erst qsort verwendet, daher auch die (bis auf die Zeigertypen) qsort-kompatible compare Funktion. Ich wollte dann aber ne deterministische Reihenfolge im Output. Und das Einsortieren selbst zu schreiben erschien mir dann einfacher/eleganter als die Compare-Funktion dementsprechend anzupassen.

    Ein Verbesserungsvorschlag (wie ichs zu Beginn im Kopf hatte) wäre evtl. im Lösungsarray einen Eintrag mehr zu haben, alles mit einem total_count = INT_MAX vorzusetzen und dann die Lösung immer direkt in den letzten Slot zu kopieren. Dann qsort aufrufen.

    Ich hatte zu anfang noch kein total_count Feld, sondern immer alles ad-hoc aufsummiert. Ich hätte natürlich INT_MAX in den ersten Counter schreiben können, aber das wollte mir einfach nicht gefallen. Plus ich wollte sehen wie viel Aufwand es wird es ohne solche Tricks zu machen.

    ps: Wobei deine Variante (also mit der theoretisch mindest nötigen Anzahl zu beginnen und dann + 1 so lange bis man genug Lösungen findet) einen Vorteil hat: es ist vermutlich viel einfacher die Obergrenze für die Laufzeit abzuschätzen. Bei meiner Variante müsste man beweisen dass schnell genug N Lösungen gefunden wurden, weil ich erst dann "throtteln" kann. Bei "guten" Stückelungen ist das kein Problem, aber ich bin mir so gar nicht sicher ob es nicht Stückelungen gibt wo mein Code quasi ewig braucht.



  • Ich sehe schon, du bist gar nicht an der Aufgabe gescheitert, nur an dem eigenen Anspruch nochmal alles zu verbessern... 😉



  • Fand gestern noch eine library für Kombinatorik discreture.



  • das ist ja auch wieder c++. 👍🏻 passt aber generell zur gesamten verständnisfähigkeit der leute hier.🤭