Algorithmus gesucht für Supermarkt-Bonus-Zahlungen (z.B. VISA)

[dg2210]

Moin,

ich bin auf der Suche nach einem Smartphone-geeignetem Algorithmus, der die Teilnahme an zwei häufigen Bonus-Aktionen (z.B. VISA) ermöglicht.

Smartphone-geeignet bedeutet, daß er auf einem älteren Gerät mit einer "handvoll MB RAM" und ein paar dutzend MB an Plattenplatz auskommen muß und innerhalb einiger Sekunden terminieren soll.

Das Problem: ein Wochenend-Familieneinkauf umfasst n Artikel (typischerweise n < 1000) mit Einzelpreisen p1, p2 ... pn, wobei die p auch negativ sein können (z.B. Pfandbons).

Gesucht: eine Aufteilung des Einkaufs in möglichst wenige "Körbe", so daß der Bonus an der Kasse maximiert wird. Konkret: der Algorithmus soll mir sagen, welche Artikel ich in welcher Reihefolge auf das Kassenband legen muß und wann der Kassiervorgang stattfinden soll, wobei als Nebenbedingung der Einsatz der negativen Preise minimiert werden soll.

Das soll für die zwei typischen Aktionen erfolgen:

Typ 1: Maximalumsatz 25 EUR, Bonus 2% vom Umsatz ( = aktuelle VISA-Aktion)

Typ 2: Aufrunden zum nächsten vollen EUR (= VISA-Aktion im Herbst 2021). Unabhängig von der Gesamtsumme gibt es die Differenz zum nächsten vollen EUR als Bonus. Beispiel: Einkauf von 12,88 gibt einen Bonus von 13 EUR - 12,88 EUR = 0,12 EUR.

Beispiel:

Ich habe 5 Artikel zu 8, 10, 12, 16 und 26 EUR und einen Pfandbon in Höhe von 1,50 EUR.

Bei Aktionen vom Typ 1 soll mir der Algorithmus sagen, drei Körbe zu machen und diese getrennt abzurechnen: (8, 16), (10,12),(26, -1,50)

Die Schwierigkeit: das Problem hat sehr große Ähnlichkeit mit dem Rucksack-Problem, welches ja leider NP-vollständig ist...Der offensichtliche Ansatz, einfach alle Permutationen durchzuprobieren, ist bei mehr als 50 Artikeln auch nicht zielführend. Die Triviallösung (jeden Artikel einzeln bezahlen) ist nervtötend und daher inakzeptabel.

Ich weiß, dass vor einigen Jahren eine ähnliche Aufgabe bei einem Informatik-Wettbewerb (entweder Informatik-Olympiade oder Bundeswettbewerb) gestellt wurde und dies mit einem Graph-Algorithmus gelöst werden konnte. Ich habe die Unterlagen nicht mehr und kann sie auch online nicht mehr finden.

Hat einer von Euch eine Idee?

Das Problem vom Typ 2 (aufrunden) lässt sich auf das Problem 1 reduzieren, wenn man statt der Einzelpreise die Differenz zum nächsten EUR nimmt und diese maximiert.

[CurtisNewton]

Bevor man versucht die optimale Lösung zu finden kann man auch zunächst mal versuchen eine näherungsweise Lösung zu finden die nur "gut" ist.

Beispiel für Typ 1:

In einer Schleife 

- Teuersten Artikel <= 25 EUR nehmen

- Schauen ob es einen weiteren oder mehrere Artikel gibt mit denen man zusammen unter 25 bleibt

Auf die Weise findest Du in zwei Iterationen  die Pärchen 16-8 und 12-10

Sinngemäß das gleiche dann für Artikel > 25 EUR und Pfandbons.

Damit findest Du eine gute Lösung aber unter Umständen nicht die Beste.

[__dpk]

@dg2210 

Sag mir bitte Bescheid wann und wo Du die Ware nach diesem Algorithmus aus dem Einkaufswagen auf das Kassenband legst, damit ich sicherstellen kann, dass ich nicht in der Warteschlange hinter Dir stehe…  😉

[JRK]

Nervtötend sind vor allem Menschen, die alle anderen an der Kasse warten lassen, nur weil Sie noch ein Paar Cent absahnen wollen.

[ehemaliger Nutzer]

---

@JRK  schrieb:

Nervtötend sind vor allem Menschen, die alle anderen an der Kasse warten lassen, nur weil Sie noch ein Paar Cent absahnen wollen.

---

Hmmm, ganz so schlimm finde ich das nicht. In den 30 Sekunden, die man eventuell länger wartet, wird man ja die Welt nicht wirklich verändern. Mich nervt es immer extrem, wenn mir die Leute an der Kasse so extrem auf die Pelle rücken. Wir haben immer noch Pandemie und 1,50 Meter Abstand ist jetzt nicht so schwer. Und es geht auch nicht schneller, nur weil man 30 cm neben mir steht, während ich mein Portemonnaie einpacke.

Grüße aus dem Supermarkt

Sonni