Script zur Ermittlung des passenden Gutscheins

  • Hallo liebe AutiIT Gemeinde,


    wollte mir ein einfaches Script schreiben, dass wie folgt funktionieren soll:

    Es gibt verschiedene Gutscheine mit verschiendenen Beträgen und Rabatten:


    Gutscheinart 1:

    Wert 44€, Rabatt 2,64€ = 6%

    Wert 20€, Rabatt 1,20€ = 6%

    Wert 5€, Rabatt 0,30€ = 6%


    Gutscheinart 2:

    Wert 80€, Rabatt 5,00€ = 6,25%

    Wert 25€, Rabatt 2,00€ = 8%

    Wert 10€, Rabatt 0,90€ = 9%

    Wert 5,5€, Rabatt 0,50€ = 9,09%


    Gutscheinart 3:

    Wert 500€, Rabatt 40,00€ = 8%

    Wert 100€, Rabatt 8,00€ = 8%

    Wert 50€, Rabatt 4,00€ = 8%


    Der Startwert wird eingetragen und es wird ermittelt welche Gutscheine am besten verwendet werden, damit der möglichst höchste Rabatt entsteht. In Summe dürfen aber nur 3 Gutscheine verwendet werden.

    Aktuell arbeitet mein Script so, dass es möglichst den höchsten Gutschein verwendet solange, bis entweder der Startbetrag möglichst ausgefüllt ist oder 3 Gutscheine verwendet werden.

    Nun soll aber auch eine Logik eingebaut werden, die prüft, ob man bspw. 2 x 10 € hernehmen könnte (=9% Rabatt) anstelle eines 20€ Gutscheins (=6% Rabatt)


    Ich bekomme die beiden Welten nicht zusammen, sodass einerseits der Betrag möglichst ausgenutzt wird (hohe Gutscheine) und andererseits möglichst die Gutscheine verwendet werden sollen, die mehr Rabatt geben (niedrige Gutscheine) immer mit max. 3 Gutscheinen in Summe.


    Am Ende wäre es schön, wenn das Script dann nicht nur den Rabatt und den Endbetrag ausspuckt, sondern auch welche Gutscheine in welcher Menge verwendet wurden.


    Ich hoffe ich habe es verständlich erklärt.

    Würde mich freuen, wenn mir hier jemand weiterhelfen könnte.


    Anbei mein Script, ich habe mir dazu bereits einiges an Gedanken gemacht:


    Viele Grüße

    Inferior

  • Die Anzahl der Gutscheine ist hier ziemlich überschaubar.
    Daher ist es kein Problem einfach alle möglichen Gutscheinkombinationen zu ermitteln und diese einzeln durchzugehen.


    Welche Auswirkung die Art des Gutscheins hat habe ich aus deiner Erläuterung noch nicht verstanden - du wertest sie ja auch nicht in deinem Skript aus.
    Im folgenden Beispielskript habe ich die Art daher frecherweise einfach als Anzahl genommen wie oft der jeweilige Gutschein vorliegt.


    Im Grunde habe ich mal folgendes gemacht: Jeden Gutschein so oft er existiert als Einzelgutschein zum Gutscheinarray hinzugefügt.
    So dass ein Gutschein, welchen man 2x hat auch 2x im Array existiert.
    Dann habe ich von dieser Gutscheinliste alle möglichen Kombinationen (sowohl 1x, 2x, als auch 3x) erstellt.
    Das Ergebnisarray beinhaltet einfach nur die Indizes im Ausgangsarray.

    Dann muss man im Grunde nur noch diese Kombinationen durchgehen und schauen bei welcher Kombi der Rabatt am höchsten ist.


    Zugegeben: Es ist aktuell nur schnell dahingerotzt. Da kann/muss man noch deutlich im Code aufräumen.
    Alternativ könnte man auch die Kombinationserstellung auch direkt (so wie du) in den Berechnungsteil schieben aber da fehlt mir gerade die Zeit da eine clevere Kombinatorik bisschen nachdenken erfordert.
    Eventuell bringt es dich dennoch ein Stück weiter:


  • Hallo AspirinJunkie,


    vielen lieben Dank für deine Ausarbeitung und die Zeit die du dir für mein kleines Projekt genommen hast.

    Ich konnte schon einiges aus deinem Code lernen und er bringt auf alle Fälle einen tollen Ansatz um darauf aufzubauen!


    Die Auflistung aller möglichen Kombinationen ist nicht notwendig. Die Gutscheinart ist nur bei der Ausgabe dann interessant. -> Nehme Gutschein 10€, Gutscheinart 2 = Spezialangebot ABC und bekomme 0,9€ Rabatt.

    Der Abschnitt kann also weggelassen werden.


    Was nun noch fehlt ist folgendes: Die Funktion _ArrayCombinations zieht nicht in Betracht, dass auch die gleichen Gutscheinkombinationen möglich wären:


    0|0

    1|1

    ...

    9|9


    0|0|0

    1|1|1

    ...

    9|9|9


    Ich habe es nicht geschafft das einzubauen, da _ArrayCombinations erst mal eine andere Logik hat.

    Kann man das noch irgendwie ergänzen?


    Vielen lieben Dank vorab.


    Viele Grüße

    Inferior

  • Die Auflistung aller möglichen Kombinationen ist nicht notwendig.

    Äh doch - über diese Liste iterieren wir ja bei der Ermittlung, welche Kombination die beste ist.


    Was nun noch fehlt ist folgendes: Die Funktion _ArrayCombinations zieht nicht in Betracht, dass auch die gleichen Gutscheinkombinationen möglich wären:

    Doch wird in Betracht gezogen. Dies wird dadurch umgesetzt, dass Gutscheine, welche mehrmals vorliegen auch mehrmals im Array $aScheine vorkommen (bei mir habe ich ja als Anzahl für die Gutscheine die Art eingesetzt). Die anschließende Kombination darauf bringt dann auch Kombis bei welchem Gutscheine mehrmals verwendet werden.
    Gib z.B. mal als Startbetrag 250 ein und du wirst eine Lösung erhalt bei der der 100€-Gutschein 2x verwendet wird.

  • Äh doch - über diese Liste iterieren wir ja bei der Ermittlung, welche Kombination die beste ist.

    Ich vermute die Verwirrung kommt daher, dass ich im Array $aGutscheine in der Dimmension 3 (0 bis 4) = Gutscheinart die Zahlen 1 bis 3 angegeben habe. Dort könnte aber auch stehen: "grün, gelb, blau"

    Anders gesagt, diese Zahl soll wiederspiegeln, dass es sich dabei um verschiedene Gutscheinarten handeln kann. Nicht aber, dass Gutschein mit der 3 öfter verwendet werden kann als einer mit einer 1.



    Doch wird in Betracht gezogen. Dies wird dadurch umgesetzt, dass Gutscheine, welche mehrmals vorliegen auch mehrmals im Array $aScheine vorkommen (bei mir habe ich ja als Anzahl für die Gutscheine die Art eingesetzt). Die anschließende Kombination darauf bringt dann auch Kombis bei welchem Gutscheine mehrmals verwendet werden.
    Gib z.B. mal als Startbetrag 250 ein und du wirst eine Lösung erhalt bei der der 100€-Gutschein 2x verwendet wird.

    Prinzipiell liegen alle Gutscheine in unendlichfacher Anzahl vor. Einziges Nadelöhr ist, dass in Summe nur 3 Gutscheine verwendet werden können. Egal welche Höhe und welche Gutscheinart.


    EDIT:

    Ich habe derweil dieses UDF gefunden, was ich prinzipiell schon sehr gut finde:

    Array combinations
    Anyone know if a function already exists for an output like this? _ArrayCombinations() doesnt quite do this. Thanks. Local $aArray = [A, B, C] #cs A B C AA AB…
    www.autoitscript.com


    Leider sind die Kombinationen im zurückgegebenen Array ohne Trennzeichen.

  • Prinzipiell liegen alle Gutscheine in unendlichfacher Anzahl vor. Einziges Nadelöhr ist, dass in Summe nur 3 Gutscheine verwendet werden können. Egal welche Höhe und welche Gutscheinart.

    Wie du sagst muss das Ausgangsarray nur verdreifacht werden und fertig.

    In meinem Skript oben einfach dazu nur Zeile 25 ändern zu For $j = 2 To 3.

    Und schon werden auch Kombinationen gefunden wo jeder Gutschein 3x vorkommen kann.


    Wie gesagt das ist alles noch eher dahingerotzt.
    Man könnte das ganze ziemlich verschlanken wenn man eine Kombination mit Repetition implementiert.
    Mach ich bestimmt auch nochmal - da brauche ich aber bisschen den Kopf frei und ebenso bisschen Zeit.


    Ich vermute die Verwirrung kommt daher, dass ich im Array $aGutscheine in der Dimmension 3 (0 bis 4) = Gutscheinart die Zahlen 1 bis 3 angegeben habe. Dort könnte aber auch stehen: "grün, rot, blau"

    Das war jetzt nicht verwirrend.
    Mir war schon klar, dass die Art wohl etwas anderes angeben soll.
    Aus der Aufgabenstellung war aber nicht ersichtlich ob die Gutscheinanzahl jeweils variabel ist.
    Daher habe ich es gleich mit so implementiert und die Art einfach beispielhaft hierzu als Attribut missbraucht.

  • Du hast völlig recht. Jetzt habe ich die Logik komplett verstanden.

    Mein Fehler!


    Die Lösung funktioniert erst mal und es sollte nun immer die beste Kombination rauskommen.

    Wie du schon geschrieben hast, ist es erst mal sozusagen "quick & durty" aber es macht was es soll.


    Vielen lieben Dank dir, du hast mir sehr geholfen.

  • Wie gesagt das ist alles noch eher dahingerotzt.
    Man könnte das ganze ziemlich verschlanken wenn man eine Kombination mit Repetition implementiert.
    Mach ich bestimmt auch nochmal - da brauche ich aber bisschen den Kopf frei und ebenso bisschen Zeit.

    So wie versprochen hier noch die algorithmisch saubere Implementierung.
    Diese sollte auch deutlich fixer ablaufen, da nun jede zu betrachtende Kombination wirklich nur 1x vorkommt:



    Für mehrmaliges Berechnen kann man das Skript noch weiter optimieren indem man für alle Gutscheinkombis den Gesamtbetrag der Gutscheine und deren Rabattsumme einmalig berechnet und in ein Array abspeichert.
    Anschließend noch nach dem Betrag und dem Rabatt sortieren und die Suche dann als binäre Suche implementieren.
    Dann wird es richtig fix.

  • Hallo AspirinJunkie,


    vielen Dank für die Zeit die du dir genommen hast.

    Meine Antwort hat leider ne Weile gedauert.

    Ich musste mir auch erst mal deine Lösung genauer ansehen.


    Nach längerem Überlegen habe ich denke ich alles verstanden.

    Eine sehr clevere Lösung.


    Du hast sogar mit eingebaut, dass er möglichst die Lösung mit den wenigsten Gutscheinen (Anzahl) verwenden soll.

    Das ist das einzige was nicht funktioniert hat.


    Ich meine den Fehler gefunden zu haben:

    If ($nRabatt = $nRabattMax) and ($iRabattMaxN >= UBound($aIndGroup)) Then ContinueLoop

    Zeile 61 müsste meiner Meinung nach heißen: If ($nRabatt = $nRabattMax) and ($iRabattMaxN <= UBound($aIndGroup)) Then ContinueLoop

    Das hat bei mir geholfen.


    Super Forum und klasse für deine Unterstützung!


    Liebe Grüße

    Inferior

  • Du hast sogar mit eingebaut, dass er möglichst die Lösung mit den wenigsten Gutscheinen (Anzahl) verwenden soll.

    Das ist das einzige was nicht funktioniert hat.


    Ich meine den Fehler gefunden zu haben:

    Zeile 61 müsste meiner Meinung nach heißen: If ($nRabatt = $nRabattMax) and ($iRabattMaxN <= UBound($aIndGroup)) Then ContinueLoop

    Super gesehen. Genau dort liegt ein Fehler.

    Du hast definitiv das Skript verstanden :thumbup: