Wechselgeld 5 besten Kombinationen


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


  • Gesperrt

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


  • Gesperrt

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