Wechselgeld 5 besten Kombinationen


  • Mod

    @Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

    Erstmal hat die Realität nichts damit zu tun, was die korrekte Lösung für eine theoretische Aufgabe ist

    die theoretische aufgabe lautete "programmieren zu lernen", nicht "kindischen schwanzvergleich abziehen"

    Wenn du nicht siehst, dass deine Lösung das Ziel verfehlt, und auch nicht verstehst, was theoretische Abstraktionen damit zu tun haben sollen, dann hast du nicht kapiert, was "Programmieren Lernen" bedeutet.



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



  • @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)


  • Gesperrt

    Dieser Beitrag wurde gelöscht!


  • @SeppJ sagte in Wechselgeld 5 besten Kombinationen:

    @Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

    Erstmal hat die Realität nichts damit zu tun, was die korrekte Lösung für eine theoretische Aufgabe ist

    die theoretische aufgabe lautete "programmieren zu lernen", nicht "kindischen schwanzvergleich abziehen"

    Wenn du nicht siehst, dass deine Lösung das Ziel verfehlt, und auch nicht verstehst, was theoretische Abstraktionen damit zu tun haben sollen, dann hast du nicht kapiert, was "Programmieren Lernen" bedeutet.

    meine lösung hat sie, glaube ich, verstanden, eure nicht. außerdem war ich ja noch gar nicht fertig.🙄

    @hustbaer sagte in Wechselgeld 5 besten Kombinationen:

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

    das war eigentlich von vornherein klar und sie hat ja auch bestimmt 10 mal gesagt, dass sie die rekursiven lösungsvorschläge alle nicht versteht - hat nur keinen interessiert. 🤦🏼♂



  • Es ist eine sache zu sagen "verstehe ich nicht" und darauf zu hoffen, das sie mir jemand erklaert, oder konkret auf spezifische dinge eingeht und erfragt.

    Mit dem ersten ansatz mangelt es an eigeninitiative und in dem fall wuerde ich auch nicht darauf eingehen.



  • @Cardiac sagte in Wechselgeld 5 besten Kombinationen:

    Mit dem ersten ansatz mangelt es an eigeninitiative und in dem fall wuerde ich auch nicht darauf eingehen.

    ja das wäre dein gutes recht. aber wenn trotzdem jemand darauf eingeht, etwa weil die eigeninitiative ihre grenzen an den - manchmal sehr seltsamen - denkweisen des vorgesetzten findet, muss man ja nicht anfangen, dumm rumzupöbeln, oder?



  • @Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

    das war eigentlich von vornherein klar und sie hat ja auch bestimmt 10 mal gesagt, dass sie die rekursiven lösungsvorschläge alle nicht versteht - hat nur keinen interessiert. 🤦🏼♂

    Und? Dann kann man ja anfangen, sich mit Rekursion zu beschäftigen, wird man früher oder später eh tun müssen. Man kann zwar jede rekursive Lösung auch iterativ umsetzen, aber das ist imho noch schwerer zu verstehen. Man hat TE eigentlich immer wieder erzählt, dass sich sowas am Besten rekursiv lösen lässt, aber weil TE bei Rekursion Verständnisprobleme hat sowas nicht haben wollte.



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


  • Gesperrt

    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.