Wechselgeld 5 besten Kombinationen

Quiche Lorraine

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 ...

DocShoe

Vielleicht kennt der Bankautomat auch seinen Bestand an Scheinen und berücksichtigt den beim Vorschlag der Stückelungen.

@EinNutzer0 sagte in Wechselgeld 5 besten Kombinationen:

es ist C++ und wahrscheinlich nicht leicht nach C übertragbar

sehe ich das richtig? man müsste erst einmal c++ lernen, um dein programm richtig zu verstehen und nach C umwandeln zu können, weil du eben kein C und damit auch kein vernünftiges beispiel kannst. oh mann!

TGGC

Automaten haben normal nur 4 Arten Scheine und rechnen teils auch den Bestand ein, geben z.B. auch eine Meldung aus, das nur Betrag x ausgezahlt werden kann, wenn z.b. 5er komplett aus sind.

@Wade1234 Quatsch, das Programm ist in 10 Min umgeschrieben, wenn man einfach feste Arrays allokiert.

wob

@codinglea

Ich würde vorschlagen, erstmal mit der einfacheren Aufgabe "Alle Lösung ausgeben" anzufangen.

Dazu braucht man nur 2 Arrays:

das mit den Scheinwerten
und ein genauso langes Array, wo man für jeden Schein speichert, wie oft man ihn gewählt hat, anfangs mit 0 initialisiert.

Schnell runtergeschrieben sieht das so aus:

#include <stdio.h>

void printSolutionResult(int scheine_size, const int *scheine, const int *auswahl) {
    int trennerBenoetigt = 0;
    for (int i = 0; i < scheine_size; ++i) {
        if (auswahl[i]) {
            if (trennerBenoetigt) printf(", "); else trennerBenoetigt = 1;
            printf("%d x %d EUR", auswahl[i], scheine[i]);
        }
    }
    puts("");
}

void findSolutions_impl(int restbetrag, int pos, int scheine_size,
                        const int* scheine, int *auswahl) {
    if (pos == scheine_size - 1) {
        if (restbetrag % scheine[pos] == 0) {
            auswahl[pos] = restbetrag / scheine[pos];
            printSolutionResult(scheine_size, scheine, auswahl);
        }
    } else {
        for (int nAktuellerSchein = restbetrag / scheine[pos];
             nAktuellerSchein >= 0; --nAktuellerSchein) {
            auswahl[pos] = nAktuellerSchein;
            findSolutions_impl(restbetrag - scheine[pos] * nAktuellerSchein,
                               pos + 1, scheine_size, scheine, auswahl);
        }
    }
}

void printSolutions(int betrag) {
    const int scheine[] = {200, 100, 50, 20, 10, 5};
    const int scheine_size = sizeof(scheine)/sizeof(scheine[0]);

    int auswahl[scheine_size];
    for (int i = 0; i < scheine_size; ++i) auswahl[i] = 0;

    findSolutions_impl(betrag, 0, scheine_size, scheine, auswahl);
}

int main(void) {
    printSolutions(150);
}

Du brauchst nur Zeile 32 zu ändern, wenn du andere Scheine hast.

Belli

@Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

@EinNutzer0 sagte in Wechselgeld 5 besten Kombinationen:

es ist C++ und wahrscheinlich nicht leicht nach C übertragbar

sehe ich das richtig? man müsste erst einmal c++ lernen, um dein programm richtig zu verstehen und nach C umwandeln zu können, weil du eben kein C und damit auch kein vernünftiges beispiel kannst. oh mann!

Sehe ich das richtig? Du müsstest erst mal C++ lernen, um sein Programm richtig zu verstehen, weil Du eben kein C++ kannst?
Oh Mann ...

codinglea

Mein Ausbilder wünscht explizit, dass ich alles in C schreibe.

@TGGC
Ich weiß gar nicht, wo dein Problem liegt. Ich bin für neue Sachen offen, allerdings sollen alle Aufgaben sehr einfach gelöst werden.
Von dir kommen(für mich noch) immer komplizierte Lösungen.

SeppJ

@codinglea sagte in Wechselgeld 5 besten Kombinationen:

Mein Ausbilder wünscht explizit, dass ich alles in C schreibe.

Ignorier' einfach alles von EinNutzer0, der ist einfach nicht hilfreich.

@TGGC
Ich weiß gar nicht, wo dein Problem liegt. Ich bin für neue Sachen offen, allerdings sollen alle Aufgaben sehr einfach gelöst werden.
Von dir kommen(für mich noch) immer komplizierte Lösungen.

Das liegt letztlich an dem, was TGGC in seiner allerersten Antwort vor langer Zeit geschrieben hat. Die Aufgabe ist uneindeutig gestellt:

@TGGC sagte in Wechselgeld 5 besten Kombinationen:

Die Aufgabe ist unterdefiniert, weil es im Allgemeinen keine genau 5 besten Kombinationen gibt. Auch geben Geldautomaten meist nicht die "besten" Kombinationen aus, sondern einige mit wenigen grossen und einige mit viele kleinen Scheinen aus.

Die Lösung wäre eigentlich zu definieren, wie "gut" eine Kombination ist und dann einfach alle zu erzeugen in einem vector, darauf sort und dann n Einträge dieses Vectors ausgeben. Wenn Güte hier einfach die Anzahl der Scheine ist, sind einige Anordnungen rein zufällig (bzw. implementationsabhängig),

Nun ist die ganz allgemeine Lösung, die mit beliebigen Scheinstückelung und einer relativ beliebigen Definition von "gut" zurecht kommt, nun einmal nicht so ganz einfach. Das ist nun einmal so. Würde man sich hingegen auf die übliche Stückelung (1, 2, 5, 10, … ) beschränken, wäre es schon viel einfacher. Wenn man dann auch noch eine günstige Definition von "gut" wählt, ist es noch besser.

EinNutzer0

Dieser Beitrag wurde gelöscht!

@codinglea läuft es denn jetzt?