Wechselgeld 5 besten Kombinationen

@codinglea sagte in Wechselgeld 5 besten Kombinationen:

mit dem Brute Force funktioniert es ja nur halbwegs...
Da gibt es anscheinend auch 4€ und 3€ Münzen.

wo hast du die denn her? also du bist dir schon darüber im klaren, dass die zahlen, die da nachher ausgegeben werden, die anzahl der jeweiligen münzen und scheine darstellen? eine verständliche ausgabe wäre dann so ein beispiel für eine spätere verbesserung. also ich habe es ausprobiert und ich bekomme 5 lösungen.

codinglea

@Wade1234
Bei mir funtkioniert es gerade gar nicht mehr.
EDIT: funktioniert wieder.

codinglea

Also... wenn ich eine 5 eingebe als Betrag, dann kommt einmal 5x 1€ raus, 1x 5€ und 4x 2€, 3x 5€ und 2x 2€, 1x 10€ und 4x 2€ usw...

DocShoe

Mein Ansatz wäre folgender:

Du bestimmst die optimale Kombination aus Scheinen/Münzen für die angeforderte Summe. Für den Euro gibt es 14 Einheiten (200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01), eine Kombination der möglichen Scheine/Münzen lässt sich also in einem std::array<unsigned int> unterbringen.

#include <array>
#include <vector>

// es gibt 14 verschiedene Scheine/Münzen
static size_t const DenominationCount = 14;

// in 1 Cent Einheiten
using Denominations_t 			= std::array<unsigned int,DenominationCount>;
Denominations_t CurrencyDenominations 	= {20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1 };

Denominations_t calculate_denominations( unsigned int total )
{
       Denominations_t retval;
       ...
       return retval;
} 

vector<Denominations_t> calculate_combinations( Denominations_t const& optimal )
{
    ...
}

int main()
{
    // optimale Stückelung des Betrags €157.23 bestimmen
    Denominations_t optimal = calculate_denominations( 15723 );

   // sämtliche mögliche Kombinationen bestimmen
   std::vector<Denominations_t > combinations = calculate_combinations( optimal );

   // Ausgabe, Bestimmung der besten Kandidaten, etc.
   ...
}

Die Funktion calculate_combinations lässt sich rekursiv über eine Hilfsfunktion lösen. Dabei kann z.B. ein Betrag von 15 Cent so dargstellt werden (verkürztes Array mit 5, 2 und 1 Cent):
{ 3, 0, 0 } -> 3x5 Cent, 0x2 Cent, 0x1 Cent. Wenn du eine 5 Cent Münze weniger nimmst kommst du zu folgender Kombination: { 2, 2, 1 }. Diese Stückelungen lässt sich dann wiederum als { 2,1,3 }, und { 2,0,5 } kombinieren. Dann nimmst du zwei 5 Cent Münzen weniger und kommst auf { 1,5,0}, was sich wiederum als { 1,4,2 }, { 1,3,4 }, { 1,2,6}, { 1,1,8} und { 1,0,10 } kombinieren lässt.
Die Strategie ist also, angefangen mit der zweitniedrigsten Münze, die Münzen durch kleinere Münzen zu ersetzen und die sich Kombination zu merken. Das Ganze lässt sich prima rekursiv lösen.

codinglea

@DocShoe
Dass ich extra oben als Kategorie C angegeben habe, hast du gesehen?!

DocShoe

@codinglea
Ne, habe ich nicht, Entschuldigung, aber das macht ja nix. std::array lässt sich 1:1 durch ein C-Array ersetzen, nur für vector brauchst du eine Alternative. Wenn du dir alle Kombinationen merken möchtest brauchst du was Vergleichbares. Oder du pflegst eine Top-5 Liste, die zunächst leer ist. Wenn du einen Kandidaten gefunden hast gibt´s dann zwei Möglichkeiten:

es ist noch Platz in den Top-5: -> Kandidaten einfügen
Top-5 ist voll: wenn der schlechteste Kandidat schlechter ist als die gefundene Kombination -> schlechtesten Kandidaten durch aktuelle Kombination ersetzen

TGGC

Das hatten wir doch alles schon, hat der OP aber abegelehnt mit "hab ich noch nie benutzt und möchte ich drauf verzichten".

https://i.chzbgr.com/full/2951494144/h7FAC4598/it-takes-skill

Quiche Lorraine

@hustbaer
Nein, das meinte ich gar nicht. Ich glaube hier könnte ein Greedy Algorithmus funktionieren:

Wenn wir die optimale Lösung suchen, so liefert uns der Greedy eine optimale Lösung. Wenn ich vom höchsten Schein her anfange meinen Betrag zu begleichen, so wird jede andere Lösung mehr Scheine benötigen.

Bsp: 555€ = 1 * 500€ + 0 * 200€ + 0 * 100€ + 1 * 50€ + 1 * 5€ + ...

Das Ganze kann man durch eine eine Reihe von Divisionen und Modulo Operationen berechnen.

Wenn ich nun aber nicht mit dem 500€ Schein bezahlen möchte, muss ich die 500€ durch andere Scheine ersetzen. Dies kann ich aber auch genauso rechnen wie bei der optimalen Lösung.

555€ = 2 * 200€ + 1 * 100€ + 1 * 50€ + 1 * 5€ + ...

Ist im Endeffekt der gleiche Algorithmus wie der zur Berechnung der optimalen Lösung, nur das ich bei der Berechnung Scheine >= X ignoriere.

Das bedeutet, wenn ich die zweitbeste Lösung bestimmen möchte, so berechne ich zuerst die optimale Lösung. Danach nehme ich den höchsten verwendeten Schein der optimale Lösung und berechne hierfür die optimale Lösung ohne das ich mit diesen nutze. Die zweitbeste Lösung entspricht dann der optimalen Lösung minus höchster Schein plus der optimalen Lösung für den höchsten Schein.

Bsp.:

Betrag = 555€

Optimale Lösung = 1 * 500€ + 1 * 50€ + 1 * 5€

Höchster Schein = 500€

Optimale Lösung für 500€ ohne das ich diesen nutze = 2 * 200€ + 1 * 100€

-> Zweitbeste Lösung = (1 * 500€ + 1 * 50€ + 1 * 5€) - 1 * 500€ + (2 * 200€ + 1 * 100€) = 2 * 200€ + 1 * 100 € + 1 * 50€ + 1 * 5€

Das Ganze würde auch für die drittbeste Lösung mit 1055€ funktionieren:

Optimale Lösung = 2 * 500€ + 1 * 50€ + 1 * 5€

Höchster Schein = 2 * 500€

Optimale Lösung für 2 * 500€ ohne das ich diesen nutze = 5 * 200€

-> Drittbeste Lösung = (2 * 500€ + 1 * 50€ + 1 * 5€) - 2 * 500€ + (5 * 200€)

hustbaer

@Quiche-Lorraine sagte in Wechselgeld 5 besten Kombinationen:

Wenn wir die optimale Lösung suchen, so liefert uns der Greedy eine optimale Lösung.

Nur wenn man voraussetzt dass die Schein-Werte "vernünftig" gewählt wurden.

Scheine: 100, 90, 20, 1
Betrag: 110
Optimale Lösung: 1x 90 + 1x 20
Beste Greedy Lösung: 1x 100 + 10x 1

Quiche Lorraine

@hustbaer
Mist, stimmt

TGGC

@Quiche-Lorraine sagte in Wechselgeld 5 besten Kombinationen:

Das bedeutet, wenn ich die zweitbeste Lösung bestimmen möchte, so berechne ich zuerst die optimale Lösung. Danach nehme ich den höchsten verwendeten Schein der optimale Lösung und berechne hierfür die optimale Lösung ohne das ich mit diesen nutze. Die zweitbeste Lösung entspricht dann der optimalen Lösung minus höchster Schein plus der optimalen Lösung für den höchsten Schein.

Das ist ebenfalls nicht korrekt, denn es hiess ganz oben mal, das die besten Lösungen sich über die Anzahl Scheine definieren. D.h. man muss wenn überhaupt nicht den größten Schein zerlegen, sondern einen, der sich mit möglich wenigen einzelnen Scheinen darstellen lässt.

Aber auch das ist keine allgemeingültige Lösung, je nachdem was es für Werte gibt. Die Lösungen müssen überhaupt nicht "benachbart" sein und daher müssen dann alle Lösungen durchsucht werden, man kann dann maximal einen lower bound finden (e.g. hab 5 Lösungen mit max 10, brauch ich nicht mehr bei 11er Kombinationen suchen). Man könnte auch sinnvoll Kombinationen durchzählen...

Könnte man noch ewig diskutieren, aber das ist alles egal. Da dem OP Grundkenntnisse fehlen. Wie benutzt man eine Variable, wie eine Funktion, wie den Indexoperator etc. und ohne das einigermassen drauf zu haben wird keine lesbare Lösung rauskommen.

@codinglea also ich habe jetzt auch mal selbst den debugger verwendet.
fehler nummer 1: in der k-schleife wird m mit max_k verglichen, das ist natürlich falsch.
fehler nummer 2: du multiplizierst die anzahl der geldwerte mit den geldwerten und bei 5 ct werden dann 5 stck 5ct-münzen angezeigt, was natürlich quatsch ist. also richtigerweise müsstest du dann a, b, c, ... ausgeben und nicht a * a_wert, b * b_wert, c * c_wert, ...

@TGGC sagte in Wechselgeld 5 besten Kombinationen:

Da dem OP Grundkenntnisse fehlen. Wie benutzt man eine Variable, wie eine Funktion, wie den Indexoperator etc. und ohne das einigermassen drauf zu haben wird keine lesbare Lösung rauskommen.

gut erkannt. es hat zwar lange gedauert, bis du zu dieser einsicht gelangt bist, aber besser spät, als nie, oder wie sagt man?

TGGC

@Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

@TGGC sagte in Wechselgeld 5 besten Kombinationen:

Da dem OP Grundkenntnisse fehlen. Wie benutzt man eine Variable, wie eine Funktion, wie den Indexoperator etc. und ohne das einigermassen drauf zu haben wird keine lesbare Lösung rauskommen.

gut erkannt. es hat zwar lange gedauert, bis du zu dieser einsicht gelangt bist, aber besser spät, als nie, oder wie sagt man?

Dumm?

@TGGC sagte in Wechselgeld 5 besten Kombinationen:

@Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

@TGGC sagte in Wechselgeld 5 besten Kombinationen:

Da dem OP Grundkenntnisse fehlen. Wie benutzt man eine Variable, wie eine Funktion, wie den Indexoperator etc. und ohne das einigermassen drauf zu haben wird keine lesbare Lösung rauskommen.

gut erkannt. es hat zwar lange gedauert, bis du zu dieser einsicht gelangt bist, aber besser spät, als nie, oder wie sagt man?

Dumm?

ja das wird es sein.

EinNutzer0

Sehr schwer. Folgendes hab ich mir noch ausgedacht (es ist C++ und wahrscheinlich nicht leicht nach C übertragbar, der Betrag 555 soll berechnet werden):

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

const int n = 7;
const int werte[n] = {500, 200, 100, 50, 20, 10, 5};

int getNext(std::vector<std::vector<int>> &v1, std::vector<int> &v2, int idx, long sum)
{
    if (sum == 0)
    {
        v1.push_back(std::vector<int>(v2));
        return 1;
    }
    for (size_t i = idx; i < n; i++)
    {
        sum -= werte[i];
        if (sum >= 0)
        {
            v2[i]++;
            getNext(v1, v2, i, sum);
            //if (v1.size() >= 10)
            //{
            //    return 1;
            //}
            v2[i]--;
        }
        sum += werte[i];
    }
    return 0;
}

int main()
{
    const int sum = 555;
    std::vector<std::vector<int>> v1;
    std::vector<int> v2(n, 0);
    std::cout << getNext(v1, v2, 0, sum) << std::endl;
    std::sort(v1.begin(), v1.end(), [](const std::vector<int> &a, const std::vector<int> &b) {
        int c = std::accumulate(a.begin(), a.end(), 0);
        int d = std::accumulate(b.begin(), b.end(), 0);
        return d > c;
    });

    for (size_t i = 0; i < 10; i++)
    {
        std::cout << i + 1 << ": ";
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < v1[i][j]; k++)
            {
                std::cout << werte[j] << " ";
            }
        }
        std::cout << std::endl;
    }
    return 0;
}

0
1: 500 50 5
2: 500 20 20 10 5
3: 200 200 100 50 5
4: 200 200 50 50 50 5
5: 200 100 100 100 50 5
6: 500 20 10 10 10 5
7: 500 20 20 5 5 5
8: 200 200 100 20 20 10 5
9: 100 100 100 100 100 50 5
10: 500 20 10 10 5 5 5

...und, wären das jetzt die 10 besten oder nicht? (...wobei mir zB 9: besser gefällt als 6:)

Es ist i-wie nur schwer vorstellbar, dass am Geldautomaten lange gerechnet oder gar Random eingesetzt wird... Vielleicht sind für die üblichsten Beträge die Kombinationen einfach hinterlegt.

Belli

Man wird nicht umhin kommen, ALLE Möglichkeiten zu berechnen, und sich dann die 5 mit den wenigsten Stücken rauszusuchen.
Wobei es dabei ja dann immer Abbruchkriterien gibt, die wurden ja auch schon genannt, zB. wenn ich fünf Lösungen habe, breche ich jede weitere Berechnung ab, sobald ich auf mehr Stücke als die fünftschlechtest komme, usw. ...

TGGC

Aber auch wenns vorberechet ist, setzt sich keiner von Hand hin für alle Kombos. Beim Bankautomat ist so eine Regel wie "gib mindestens/höchstens x Euro in grossen/kleinen Scheinen" und das x variert halt für die verschiedenen Optionen. Der User wählt dann ob er grosse oder kleine Scheine bevorzugt. Die letzte Option gibt dann z.B. ein Haufen 5er Scheine und nicht möglichst wenig Scheine.

Belli

Der Geldautomat könnte denke ich sogar alles berechnen:

gibt der nur Scheine aus, keine Münzen, es gibt also nur 6 verschiedene Sorten, und
die Beträge, die man da abheben kann, sind auch limitiert.

Belli

@codinglea:
Wieso darf es eigentlich nicht C++ sein? Das würde einige Kleinigkeiten (zB. ein dynamischer Container) etwas erleichtern ...