Wechselgeld 5 besten Kombinationen



  • ja man kann sich ja auch einfach mal schnell eine ki programmieren, die nachher die beliebtesten möglichkeiten ausgibt. wer bei sowas am anfang überfordert ist, taugt eh nichts. 🙃



  • @Wade1234 Wenn du es nach 200+ beitraegen immer noch nicht verstanden hast, bist du nicht nur kritikunfaehig, sondern auch daemlich und ignorant.

    bevor du dich jetzt wieder ueber den wortlaut echauffierst; an deiner inkompetenz und mangelnder verstaendnis der dir aufgezeigten probleme aendert sich leider nichts.



  • An eine KI-Herangehensweise hatte ich auch schon gedacht, nur wird das in C äußerst sperrig. Außerdem wäre das kein 10-Zeiler mehr, und die KI muss ja auch irgendwie angelernt werden, und wer hat dazu schon Lust?

    Hätte ich eine Bank, würd ich den Kunden ihre Geldausgabe bewerten lassen: "Wie zufrieden waren Sie heute mit dem Geldautomaten auf einer Skala von 1 bis 10?", und dann damit die KI anlernen. 😅

    Aber ich denke, der einfachste zu verstehende Ansatz wäre für die TE: Rekursion + sorted linked list (ak "priority" queue) - dann muss auch nichts sortiert werden.



  • @hustbaer sagte in Wechselgeld 5 besten Kombinationen:

    Also ich hab mich gestern mal hingesetzt und das "mal schnell" selbst implementiert. Und zwar die Rekursive Variante. Ergebnis:

    • Hat ein paar Stunden gedauert.
    • ~110 Zeilen C Code (Kommentare und "lesbare Formatierung" mitgezählt).
    • Ohne Optimierung des Algorithmus läuft das ganze mit den oben angegebenen 15 Geldwerten und Input = €100 ewig.
    • Mit Optimierung geht's dann quasi "instant", nur damit man auf die Idee kommt wie man das ohne Einschränkung was die verfügbaren Schein-/Münzwerte angeht optimieren kann... also dazu braucht's schon ein bisschen Erfahrung oder reichlich viel Schlau.
    • Die Sache ist ausreichend komplex dass man da ohne weiteres auch als Erfahrener Programmierer schnell mal ein paar Fehler einbaut, die man ohne Debugger nur mühsam findet.

    Alles in allem IMO für Anfänger die noch mit den Grundlagen kämpfen viel zu krass.

    Da machste aber was falsch. Ich hab das grad in der Mittagspause in paar Minuten gemacht, maximal 20. Mit dem Abbruch nach 5 kürzesten Ausgaben läuft es problemlos in Millisekunden mit so einem onlinecompiler. Also einfach stur nach Aufgabe. Inkl. diesem Abbruchkriterium hats grad 65 Zeilen. Sehe auch keine wirklich komplizierte Sachen drin, ausser sich irgendwie ne dynamische Liste frickeln zu müssen.

    Und die Varainte für nur beste Lösung (also Teil a) ist ja nur ein primitiver 3 Zeiler, der ist auf jeden Fall geeignet.



  • @TGGC Leicht möglich dass ich was falsch gemacht habe 🙂

    Wenn ich zu Hause nochmal dran denk mach ich einen Thread zu dem Thema, damit wir die OP nicht weiter damit nerven. Eins vorweg: ich wollte eine Lösung die unabhängig von den Schein-/Münz-Werten immer korrekte Ergebnisse auswirft. Und da wüsste ich jetzt nicht wie man einfach erkennen kann dass die N besten Lösungen gefunden wurden. Kann natürlich sein dass ich es einfach nur nicht checke. Wenn ich gleich noch dran denke poste ich auf jeden Falll den Code. Wenns dir nicht zu doof ist kannst du mir dann auch gerne alles zeigen wo ich was zu kompliziert gemacht habe.



  • Also wenn man a) gelöst hat, kennt man die Länge n. Dann erzeugt man alle Kombinationen der Länge n+1 und schaut ob man nun genug Lösungen hat, usw. Wenn man a) nicht hat, kann man n auch nach unten abschätzen. Und die prinzipielle Rekursionsvorschrift für die Kombinationen hatten wir ja hier schon gesehen: https://www.c-plusplus.net/forum/topic/350274/wechselgeld-5-besten-kombinationen/122



  • @TGGC Ja gehen wir mal davon aus dass man a) noch nicht gelöst hat. Ich wüsste nämlich auch nicht wie man a) lösen sollte ohne wie du vorgeschlagen hast einfach durchzuprobieren (angefangen von einem trivial ermitteltem Minimum ala Betrag/Max-Scheingrösse).

    Aber ja, auf die Idee die max. Anzahl an Scheinen von vorn herein zu begrenzen bin ich nicht gekommen. Das macht natürlich Sinn. Ich glaube aber dass mein Code dadurch kaum signifikant kleiner wird.

    Ist aber auch wieder genau so ein Punkt wo ich sagen würde: dazu braucht man zumindest Erfahrung oder muss halbwegs gut Schlau sein.



  • Für normale Scheinverteilungen kannst du einfach Greedy wegnehmen restbegtrag / schein[n] in einer simplen for loop. Ich weiss aber nicht genau, wie man beweisen kann, das die Scheinverteilung dem genügt.


  • Mod

    Aber nicht alle möglichen Stückelungen gehorchen dieser Annahme.



  • @Quiche-Lorraine sagte in Wechselgeld 5 besten Kombinationen:

    @hustbaer
    Funktioniert deine Lösung auch mit 99999,99€?

    In der Aufgabenstellung steht nämlich:

    Fange beim Anwender eine Summe 0,01 < X < 100.000,00 ab.

    (siehe https://www.c-plusplus.net/forum/topic/350274/wechselgeld-5-besten-kombinationen/1)

    Theoretisch: ja. Praktisch wird das wohl relativ lange dauern 🙂

    Das blöde dabei ist halt dass man selbst mit dem €500 Schein dazu > 200 Scheine braucht, und ein nur begrenzt schlauer Algorithmus der halt einfach alle Möglichkeiten 200 Scheine auszuwählen durchprobiert ... naja das dauert halt ein bisschen.



  • Also hier auf jeden Fall mein Code, falls es jmd. interessiert:

    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <assert.h>
    
    #define ARRAY_SIZE(a) (sizeof(a)/sizeof((a)[0]))
    
    int const note_type_values[] = {
    	50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1
    };
    
    #define NOTE_TYPE_COUNT ARRAY_SIZE(note_type_values)
    
    typedef struct solution {
    	int total_count;
    	int note_count[NOTE_TYPE_COUNT];
    } solution;
    
    int compare_solutions(solution const* x, solution const* y) {
    	if (x->total_count > y->total_count)
    		return 1;
    	else if (x->total_count < y->total_count)
    		return -1;
    	else
    		return 0;
    }
    
    void print_solution(solution const* s) {
    	printf("total count %d -- ", s->total_count);
    	char const* delimiter = "";
    	for (int i = 0; i < NOTE_TYPE_COUNT; i++) {
    		if (s->note_count[i] > 0) {
    			printf("%s%d x %d.%02d", delimiter, s->note_count[i], note_type_values[i] / 100, note_type_values[i] % 100);
    			delimiter = ", ";
    		}
    	}
    }
    
    void get_best_solutions_impl(int remaining_amount, int max_solution_count, solution* out_solutions, int* current_solution_count, solution const* base, int first_type) {
    	if (remaining_amount == 0) {
    		// found a new solution
    		// check against current worst one
    		if (*current_solution_count < max_solution_count || compare_solutions(base, &out_solutions[max_solution_count - 1]) < 0) {
    			// new one is better
    			if (*current_solution_count < max_solution_count)
    				(*current_solution_count)++;
    			// select target index as large as possible while still retaining a sorted order
    			int target_index = *current_solution_count - 1;
    			while (target_index > 0 && compare_solutions(base, &out_solutions[target_index - 1]) < 0)
    				target_index--;
    			// move other solutions down
    			for (int i = (*current_solution_count - 1); i > target_index; i--)
    				out_solutions[i] = out_solutions[i - 1];
    			// insert new solution
    			out_solutions[target_index] = *base;
    		}
    		// since we started with a solution, irregardless of whether it was good enough or not,
    		// it doesn't make sense to add any more notes -> we're done.
    		return;
    	}
    
    	if (first_type >= NOTE_TYPE_COUNT)
    		return; // out of notes to try
    
    	int const my_value = note_type_values[first_type];
    	// max. count for "my" note. start with max. count before overshooting remaining amount.
    	int my_max_count = remaining_amount / my_value;
    
    	if (*current_solution_count == max_solution_count) {
    		// already got as many solutions as we need
    		// -> no need to try anything that isn't better than the worst current solution.
    		int const current_worst_total_count = out_solutions[max_solution_count - 1].total_count;
    		int const max_sensible_this_type_count = current_worst_total_count - base->total_count - 1;
    		if (max_sensible_this_type_count < 1)
    			return; // it wouldn't even make sense to add one single note -> we're done
    		if (my_max_count > max_sensible_this_type_count)
    			my_max_count = max_sensible_this_type_count;
    	}
    
    	solution s = *base;
    	for (int i = my_max_count; i >= 0; i--) {
    		s.note_count[first_type] = i;
    		s.total_count = base->total_count + i;
    		get_best_solutions_impl(
    			remaining_amount - i * my_value,
    			max_solution_count,
    			out_solutions,
    			current_solution_count,
    			&s,
    			first_type + 1);
    	}
    }
    
    int get_best_solutions(int target_amount, int max_solution_count, solution* out_solutions) {
    	int current_solution_count = 0;
    	solution base = { 0 };
    	get_best_solutions_impl(target_amount, max_solution_count, out_solutions, &current_solution_count, &base, 0);
    	return current_solution_count;
    }
    
    int main() {
    	solution sols[5];
    	memset(sols, 0, sizeof(sols));
    	int const n = get_best_solutions(10000, ARRAY_SIZE(sols), sols);
    	for (int i = 0; i < n; i++) {
    		printf("sol #%d: ", i + 1);
    		print_solution(&sols[i]);
    		puts("");
    	}
    }
    

    Ich hoffe das ist valides C, ich mache so wenig in C ... also Geld würde ich nicht darauf verwetten 🙂



  • @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    Dann erzeugt man alle Kombinationen der Länge n+1 und schaut ob man nun genug Lösungen hat, usw.

    Also auf niedriges n schiesst sich mein Code relativ schnell ein. Trotzdem dauert es bei n~200 und 15 Scheintypen/Münztypen ewig. Linear kann man da vermutlich noch etwas optimieren. Aber selbst wenn "etwas" Faktor 10 oder gar 100 ist, wird daraus keine schnelle Sache.



  • @SeppJ sagte in Wechselgeld 5 besten Kombinationen:

    Aber nicht alle möglichen Stückelungen gehorchen dieser Annahme.

    Ja, das meinte ich. Wie beweisst man, das die Stückelung dem genügt? Man muss glaube ich zeigen das ein c existiert für jedes a > b > c mit schein[a] + n * schein[c] == m * schein[b] wo n < m gilt. Trivial wenn n = 0 ist und a einfach ein vielfaches von b ist (20 == 2*10), aber bei 50 gilt das z.b. nicht, aber weil 50/10 nur zwei Scheine sind statt 20/20/20 ist es trotzdem safe. Ich glaube das ist hinreichend aber nicht notwendig.

    @hustbaer: Ich hab das ganze compare und einsortier Geraffel nicht und das printen passiert direkt dort wo ich die Lösung finde. Die eigentliche Rekursion ist quasi gleich. Ich finde auch bei dir ist nicht etwa das Ausrechnen der Lösung kompliziert sondern nur das selbstgemachte abspeichern und rumschieben. Ein Verbesserungsvorschlag (wie ichs zu Beginn im Kopf hatte) wäre evtl. im Lösungsarray einen Eintrag mehr zu haben, alles mit einem total_count = INT_MAX vorzusetzen und dann die Lösung immer direkt in den letzten Slot zu kopieren. Dann qsort aufrufen.



  • @Cardiac sagte in Wechselgeld 5 besten Kombinationen:

    @Wade1234 Wenn du es nach 200+ beitraegen immer noch nicht verstanden hast, bist du nicht nur kritikunfaehig, sondern auch daemlich und ignorant.

    bevor du dich jetzt wieder ueber den wortlaut echauffierst; an deiner inkompetenz und mangelnder verstaendnis der dir aufgezeigten probleme aendert sich leider nichts.

    gut bitteschön: ihr habt alle recht und meine lösung taugt nichts. zum glück ist dies hier ein freies land, in dem jeder machen kann, was er will. 🙄

    @codinglea code bitte!



  • @hustbaer sagte in Wechselgeld 5 besten Kombinationen:

    @Quiche-Lorraine sagte in Wechselgeld 5 besten Kombinationen:

    @hustbaer
    Funktioniert deine Lösung auch mit 99999,99€?

    In der Aufgabenstellung steht nämlich:

    Fange beim Anwender eine Summe 0,01 < X < 100.000,00 ab.

    (siehe https://www.c-plusplus.net/forum/topic/350274/wechselgeld-5-besten-kombinationen/1)

    Theoretisch: ja. Praktisch wird das wohl relativ lange dauern 🙂

    Das blöde dabei ist halt dass man selbst mit dem €500 Schein dazu > 200 Scheine braucht, und ein nur begrenzt schlauer Algorithmus der halt einfach alle Möglichkeiten 200 Scheine auszuwählen durchprobiert ... naja das dauert halt ein bisschen.

    Ich hab das grad mal bei mir getestet, es läuft ohne Probleme auch mit der Zahl für die Top 5. Wenn ich sage 1000 Lösungen ausgeben, kommt die Zeit langsam in sinnvoll messbare Bereiche von 1.x Sekunden. (Hab https://www.onlinegdb.com/online_c_compiler benutzt)

    Das liegt scheinbar daran, das ich doch nen ganzen Teil der Kombinationen gar nicht erst teste. Ich habe auch so einen "firstype", die höchste Münze die ich der Lösung noch hinzufüge im nächsten Rekursionsschritt, bei mir biggestCoin genannt. Damit habe ich ebenfalls ein Abbruchkriterium, wenn das Restgeld mit der restlichen Münzen nicht erreicht werden kann. Ohne kommt die gleiche Lösung raus, aber bei hohen Beträgen messbar langsamer. Siehe hier:

        if (missingMoney < 0)
        {
            return;
        }
        if (missingMoney > coinValue[biggestCoin] * missingCoins)
        {
            //even with all highest coins its not enough, this check is not necessary, but much quicker
            return;
        }
    

    Ich hab auch umgekehrt immer nur ein Münze pro Rekursionsschritt hinzugefügt, dafür alle Münztypen statt nur ein Münztyp in jeder möglichen Menge zu testen. Das ist aber glaube eher irrelevant für die Performance. Es ändert nur die Reihenfolge, es kann maximal den lower bound schnellen finden.

        for(int i = biggestCoin; i < coinCount; ++i)
        {
            // lets try coin i and do recursive call
            *nextRes = i;
            addCoin(found, nextRes + 1, missingMoney - coinValue[i], missingCoins - 1, i);
            if (*found >= maxOutput)
            {
                return;
            }
        }
    

    Ansonsten passiert bei mir auch nichts weiter. Würde das Thema aber auch weniger relevant einschätzen, weil man eh nicht zig mal mit riesigen Zahlen testen wird.


  • Mod

    @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    @SeppJ sagte in Wechselgeld 5 besten Kombinationen:

    Aber nicht alle möglichen Stückelungen gehorchen dieser Annahme.

    Ja, das meinte ich.

    Ich meinte aber was anderes: Was machst du, wenn die Stückelung dem bewiesenermaßen nicht genügt. Dann gilt schließlich nicht mehr diese Annahme zur Performanceoptimierung:

    @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    Für normale Scheinverteilungen kannst du einfach Greedy wegnehmen restbegtrag / schein[n] in einer simplen for loop.



  • @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    Ich hab auch umgekehrt immer nur ein Münze pro Rekursionsschritt hinzugefügt, dafür alle Münztypen statt nur ein Münztyp in jeder möglichen Menge zu testen. Das ist aber glaube eher irrelevant für die Performance. Es ändert nur die Reihenfolge, es kann maximal den lower bound schnellen finden.

    Produziert das nicht haufenweise Duplikate?

    Das liegt scheinbar daran, das ich doch nen ganzen Teil der Kombinationen gar nicht erst teste. Ich habe auch so einen "firstype", die höchste Münze die ich der Lösung noch hinzufüge im nächsten Rekursionsschritt, bei mir biggestCoin genannt. Damit habe ich ebenfalls ein Abbruchkriterium, wenn das Restgeld mit der restlichen Münzen nicht erreicht werden kann.

    Sowas in der Art hab ich mir auch überlegt, hatte mir aber gedacht dass es vermutlich kaum was bringen wird. Ich werd das mal bei mir noch einbauen und schauen was dann mit 99999,99 geht 🙂



  • @SeppJ sagte in Wechselgeld 5 besten Kombinationen:

    @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    @SeppJ sagte in Wechselgeld 5 besten Kombinationen:

    Aber nicht alle möglichen Stückelungen gehorchen dieser Annahme.

    Ja, das meinte ich.

    Ich meinte aber was anderes: Was machst du, wenn die Stückelung dem bewiesenermaßen nicht genügt. Dann gilt schließlich nicht mehr diese Annahme zur Performanceoptimierung:

    @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    Für normale Scheinverteilungen kannst du einfach Greedy wegnehmen restbegtrag / schein[n] in einer simplen for loop.

    Dann muss man dann alles durchprobieren, was man für die Top5 eh muss. Aber da das Array nicht zu den Eingabedaten gehört, kann man diese Entscheidung statisch treffen. Im Endeffekt ändert sich nur wie und wie gut man die kürzeste Lösung schätzen kann. Man kann auch einfach 0 nehmen auf Kosten der Performance oder Betrag / schein[0].

    @hustbaer: Es gibt keine Duplikate, weil jede erzeugte Kombination ein monoton fallendes Array ist (50/10 ist eine Lösung für 60, 20/20/20 auch, aber 10/50 nicht). Und das die Extra-Bedingung so effizient ist, hab ich auch erst rausgefunden als ich sie testweise bei hohem Betrag man auskommentier hatte.



  • @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    @hustbaer: Es gibt keine Duplikate, weil jede erzeugte Kombination ein monoton fallendes Array ist (50/10 ist eine Lösung für 60, 20/20/20 auch, aber 10/50 nicht).

    Danke, manchmal steh ich ein bisschen auf dem Schlauch 🙂



  • @hustbaer Dein note type values Array ist falsch herum aufgebaut, daher die schlechte Performance.

    Du hättest quasi von mir abschreiben können.