Wechselgeld 5 besten Kombinationen



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



  • @TGGC Habs jetzt ausprobiert, nochmal danke fĂŒr den Tip!
    Genau eine Zeile Änderung in meinem Code (zwei wenn man das geĂ€nderte Kommentar mitzĂ€hlt)...

    		//if (max_sensible_this_type_count < 1)
    		//	return; // it wouldn't even make sense to add one single note -> we're done
    		if (max_sensible_this_type_count * my_value < remaining_amount)
    			return; // we can't reach the target using fewer notes than the worst solution -> we're done
    

    ...und schon lĂ€uft es wie Schmidts Katze - braucht damit auch fĂŒr die geforderten €99999,99 "so gut wie nix". Selbst wenn ich damit die besten 1000 Lösungen fĂŒr €99999,99 berechne braucht die eigentliche Berechnung (=ohne printf) nur ~6 ms.

    Ich finde auch bei dir ist nicht etwa das Ausrechnen der Lösung kompliziert sondern nur das selbstgemachte abspeichern und rumschieben.

    Ich hatte erst qsort verwendet, daher auch die (bis auf die Zeigertypen) qsort-kompatible compare Funktion. Ich wollte dann aber ne deterministische Reihenfolge im Output. Und das Einsortieren selbst zu schreiben erschien mir dann einfacher/eleganter als die Compare-Funktion dementsprechend anzupassen.

    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.

    Ich hatte zu anfang noch kein total_count Feld, sondern immer alles ad-hoc aufsummiert. Ich hĂ€tte natĂŒrlich INT_MAX in den ersten Counter schreiben können, aber das wollte mir einfach nicht gefallen. Plus ich wollte sehen wie viel Aufwand es wird es ohne solche Tricks zu machen.

    ps: Wobei deine Variante (also mit der theoretisch mindest nötigen Anzahl zu beginnen und dann + 1 so lange bis man genug Lösungen findet) einen Vorteil hat: es ist vermutlich viel einfacher die Obergrenze fĂŒr die Laufzeit abzuschĂ€tzen. Bei meiner Variante mĂŒsste man beweisen dass schnell genug N Lösungen gefunden wurden, weil ich erst dann "throtteln" kann. Bei "guten" StĂŒckelungen ist das kein Problem, aber ich bin mir so gar nicht sicher ob es nicht StĂŒckelungen gibt wo mein Code quasi ewig braucht.



  • Ich sehe schon, du bist gar nicht an der Aufgabe gescheitert, nur an dem eigenen Anspruch nochmal alles zu verbessern... 😉



  • Fand gestern noch eine library fĂŒr Kombinatorik discreture.



  • das ist ja auch wieder c++. đŸ‘đŸ» passt aber generell zur gesamten verstĂ€ndnisfĂ€higkeit der leute hier.đŸ€­