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?

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?

TGGC

@SeppJ sagte in Wechselgeld 5 besten Kombinationen:

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.

Man muss aber dazu sagen, das sie ist aber auch nicht so schwer ist. Man muss sich mit Arrays, Divide'n'Conqer und Sortieren auskennen - was alles komplette Grundlagen sind und jeder produktiv arbeitende Programmierer lange im Schlaf kann. Diese ganze Rumgekrebse um dies krampfhaft zu umgehen und eine "simplere" Lösung zusammenzufrickeln ist reine Zeitverschwendung mit der man am Ende 0 gewinnt. So lange wie der Thread läuft hätte man diese drei Prinzipien auch längst durchdringen können. Bis aufs letztendliche Sortieren wurden ja hier auch schon Lösungen gezeigt.

SeppJ

Das ist wahr.

Oft sind allgemeine Lösungen ja sogar einfacher zu programmieren, laufen bloß länger. Hier hat man halt den Sonderfall, dass bei einer 1-2-5-Stückelung der Algorithmus zum Finden der "besten" Lösung ein ganzes Stück einfacher ist als im allgemeinen Fall und man sich dann daran hochhangeln könnte. Wenn man denn könnte. Hier fehlt das intuitive Verständnis für die grundlegenden Sprachmittel, die von dir genannt wurden, die die Notwendigkeit sind, damit man ein intuitives Verständnis für Algorithmen entwickeln kann. Ich empfehle, ein paar einfachere Übungsaufgaben zu versuchen. Oder vor allem Übungsaufgaben, die irgendeinem didaktischen Plan folgen. Diesen Mangel hat man schon bei der vorherigen Fragestellung von codinglea gemerkt, die überhaupt nicht für C auf dem Level geeignet war. Und jetzt schon wieder so etwas. Ich möchte die Kompetenz der Lehrkraft bei der Wahl dieser Aufgaben anzweifeln (Oder es ist ein fortgeschrittener Kurs und codinglea ist ganz weit abgehängt, kann man als Außenstehender schließlich nicht beurteilen).

TGGC

Für die Beste - ja. Fürs Fünftbeste geht aber schon vorhersehbar die Frickelei los. So kann es vom Lehrenden nicht gedacht sein, entweder hat der sich wirklich gar nichts dabei gedacht (wie ich schon vermutete, das man so eine Ausbilding sich auch sparen kann) oder lea bekommt es 0 auf die Kette obwohl die Sachen schon soweit vermittelt wurden.