1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus

@TGGC sagte in 1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus:

@Schlangenmensch
int calc(int s, int l, int* c)
{
if (l < 2) return s % c[l] ? 0 : 1;
if (s < c[l] ) return calc(s,l-1, c);
return calc(s,l-1,c) + calc(s-c[l],l,c);
}

bist du dir sicher, dass das funktioniert? bzw. was ist denn genau s, was l und was c? also ich bekomme als ergebnis immer 66.

@Luckyingmar mach dir halt erstmal gedanken, wie du die kombinationen alle zusammen bekommst.

TGGC

@Wade1234 sagte in 1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus:

@TGGC sagte in 1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus:

@Schlangenmensch
int calc(int s, int l, int* c)
{
if (l < 2) return s % c[l] ? 0 : 1;
if (s < c[l] ) return calc(s,l-1, c);
return calc(s,l-1,c) + calc(s-c[l],l,c);
}

bist du dir sicher, dass das funktioniert? bzw. was ist denn genau s, was l und was c? also ich bekomme als ergebnis immer 66.

Ja funktioniert wenn korrekt aufgerufen, möchte aber 1:1 kopieren verhindern. Wie genau ist oben erklärt.

Th69

@TGGC: Es muß bei deinem Code aber if (l < 1) heißen, sonst kommt z.B. bei 5 nur 1 und nicht 4 heraus!

TGGC

@Th69
Nein, ist auch anders lösbar entsprechend meiner ursprünglichen Definition.

also ich habe heute mal ein bisschen herumprobiert:

der naive bruteforce-ansatz von oben mit einer kleinen zusätzlichen optimierung, sehr schnell aber unflexibel:

#include <stdio.h>
#include <time.h>

#define ival 10
#define jval 5
#define kval 2
#define lval 1

int main()
{
        int i, j, k, l;
        int maxi, maxj, maxk, maxl;

        int betrag;
        int anzahl;

        struct timespec t1, t2;

        printf("betrag: ");
        scanf("%d", &betrag);

        maxi = betrag / ival;
        maxj = betrag / jval;
        maxk = betrag / kval;
        maxl = betrag / lval;

        clock_gettime(CLOCK_REALTIME, &t1);

        anzahl = 0;

        for(i = 0; i <= maxi; i++)
        {
                for(j = 0; j <= maxj; j++)
                {
                        if(i * ival + j * jval > betrag)
                        {
                                break;
                        }

                        for(k = 0; k <= maxk; k++)
                        {
                                if(i * ival + j * jval + k * kval > betrag)
                                {
                                        break;
                                }

                                for(l = 0; l <= maxl; l++)
                                {
                                        if(i * ival + j * jval + k * kval + l * lval > betrag)
                                        {
                                                break;
                                        }

                                        if(i * ival + j * jval + k * kval + l * lval == betrag)
                                        {
                                                anzahl++;
                                        }
                                }
                        }
                }
        }

        clock_gettime(CLOCK_REALTIME, &t2);

        printf("anzahl: %d\n", anzahl);
        printf("zeit: %ld s %ld ns\n", t2.tv_sec - t1.tv_sec, t2.tv_nsec - t1.tv_nsec);

        return 0;
}

root@FreeBSD:/home/ralf # cc -O2 -o kombtest3 kombtest3.c && ./kombtest3
betrag: 1000
anzahl: 1712051
zeit: 1 s 405792806 ns
root@FreeBSD:/home/ralf # cc -O2 -o kombtest3 kombtest3.c && ./kombtest3
betrag: 2000
anzahl: 13514101
zeit: 21 s 397108443 ns

der rekursive ansatz, sehr übersichtlich aber unglaublich langsam:

#include <stdio.h>
#include <time.h>

int calc_rek(int betrag, int nummer, int werte[])
{
        if(betrag == 0)
        {
                return 1;
        }

        if(betrag < 0 || nummer == 4)
        {
                return 0;
        }

        return calc_rek(betrag - werte[nummer], nummer, werte) + calc_rek(betrag, nummer + 1, werte);
}

int main()
{
        int betrag;
        int anzahl;
        int werte[] = {10, 5, 2, 1};

        struct timespec t1, t2;

        printf("Betrag: ");
        scanf("%d", &betrag);

        clock_gettime(CLOCK_REALTIME, &t1);
        anzahl = calc_rek(betrag, 0, werte);
        clock_gettime(CLOCK_REALTIME, &t2);

        printf("anzahl: %d\n", anzahl);
        printf("zeit: %ld s %ld ns\n", t2.tv_sec - t1.tv_sec, t2.tv_nsec - t1.tv_nsec);

        return 0;
}

root@FreeBSD:/home/ralf # cc -O2 -o kombtest kombtest.c -lpthread && ./kombtest
Betrag: 1000
anzahl: 1712051
zeit: 12 s -175423158 ns
root@FreeBSD:/home/ralf # cc -O2 -o kombtest kombtest.c -lpthread && ./kombtest
Betrag: 2000
anzahl: 13514101
zeit: 188 s 37553069 ns

der "hybrid-ansatz", genauso flexibel wie der rekursive ansatz, aber etwa doppelt so schnell.

#include <stdio.h>
#include <time.h>

int loopfunc(int betrag, int summe, int nummer, int werte[], int numwerte)
{
        int i;
        int maxi;

        int anzahl;
        int summeneu;

        anzahl = 0;

        if(nummer == numwerte)
        {
                return 0;
        }

        maxi = betrag / werte[nummer];

        for(i = 0; i <= maxi; i++)
        {
                summeneu = summe + i * werte[nummer];

                if(summeneu == betrag)
                {
                        anzahl++;
                        continue;
                }

                if(summeneu > betrag)
                {
                        return anzahl;
                }

                anzahl = anzahl + loopfunc(betrag, summeneu, nummer + 1, werte, numwerte);
        }

        return anzahl;
}

int main()
{
        int betrag;
        int anzahl;
        int werte[] = {10, 5, 2, 1};

        struct timespec t1, t2;

        printf("betrag: ");
        scanf("%d", &betrag);

        clock_gettime(CLOCK_REALTIME, &t1);
        anzahl = loopfunc(betrag, 0, 0, werte, 4);
        clock_gettime(CLOCK_REALTIME, &t2);

        printf("anzahl: %d\n", anzahl);
        printf("zeit: %ld s %ld s\n", t2.tv_sec - t1.tv_sec, t2.tv_nsec - t1.tv_nsec);

        return 0;
}

root@FreeBSD:/home/ralf # cc -O2 -o kombtest2 kombtest2.c -lpthread && ./kombtest2
betrag: 1000
anzahl: 1712051
zeit: 6 s -39405363 s
root@FreeBSD:/home/ralf # cc -O2 -o kombtest2 kombtest2.c -lpthread && ./kombtest2
betrag: 2000
anzahl: 13514101
zeit: 93 s -871818673 s

@Luckyingmar lesen, verstehen, selber programmieren!

SeppJ

Du solltest deine Zeitberechnung überdenken. Zeit zwischen 15. Oktober und 6. Dezember ist nach dir 2 Monate und -9 Tage.

jetzt wo dus sagst verstehe ich auch, wo die negativen zahlen herkommen.

Th69

@TGGC sagte in 1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus:

@Th69
Nein, ist auch anders lösbar entsprechend meiner ursprünglichen Definition.

Naja, bei if (l < 1)kommen auf jeden Fall für die ersten Werte die richtigen Zahlen heraus: Ideone-Code.
Und bei deinem Code nicht!

Nur damit wir das selbe meinen (für 1, 2, 5, 10):


1:
1

2:
2
1+1

3:
2+1
1+1+1

4:
2+2
2+1+1
1+1+1+1

5:
5
2+2+1
2+1+1+1
1+1+1+1+1

...

Oder meinst du etwas anderes?

Edit: OK, jetzt weiß ich, wie du es aufrufst: geänderter Ideone-Code
Aber das ergibt logisch keinen Sinn, die 0 dort zum Array hinzuzufügen...

TGGC

@Th69
Weil du die falschen Daten übergibst. Schau in meinen ersten Post, welche Werte in dem Array stehen sollen.

Th69

Du meinst diesen (Fettdruck von mir)?
@TGGC sagte in 1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus:

Man kann da ganz simpel eine Formel herleiten und rekursiv berechnen. Angenommen wir haben die Münzen aufsteigend geordnet als m1,m2... und wir haben die Summe s, die man bilden soll und suchen nun Anzahl(s,m1,m2,...,mn) dann gilt folgendes:
Anzahl(s,m1,m2,...,mn) = Anzahl(s - mn,m1,m2,...,mn) + Anzahl(s,m1,m2,...,mn-1)

Was genau bedeudet das? Nehmen wir ein konkretes Beispiel! Ich soll 13 cent bauen aus 1,2,5. Wenn ich die 13 cent baue, habe ich 2 Möglichkeiten, ich habe mindestens eine 5 dabei, oder ich habe keine 5 dabei. Die Anzahl ohne 5 ist Anzahl(s,m1,m2,...,mn-1), die Anzahl mit einer 5 ist Anzahl(s - mn,m1,m2,...,mn). Konkret ist das erste Anzahl(13,1,2) und das zweite Anzahl(8,1,2,5). Diese beiden Möglichkeiten muss ich nun nur noch addieren um auf meine Gesamtmöglichkeiten zu kommen.

Logischerweise ist Anzahl(n,1) =1 und Anzahl(s,m1,m2,...,mn) == Anzahl(s,m1,m2,...,mn-1) wenn mn > s und das war quasi schon.

Was soll dann an dem Array falsch sein? Kannst du mal etwas konkreter werden?

Edit (nach einem Tag): Keine Antwort ist auch 'ne Antwort.

TGGC

Das Array sollte die oben genannten Werte für die Funktion "Anzahl" enthalten.

Th69

Sorry, ich verstehe's immer noch nicht.
Wie sieht bei dir konkret der Aufruf der Funktion calc aus?

TGGC

Dieser Beitrag wurde gelöscht!

TGGC

calc(s, n, [s,m1,m2,...,mn-1,mn]);

Th69

OK, statt der 0 (wie ich in meinem "Edit" schon geschrieben habe) übergibst du also s als ersten Wert im Array. Aber das ist genauso sinnlos (da vom Algorithmus niemals darauf zugegriffen wird und s wird ja schon als 1. Parameter übergeben).

TGGC

Nein, das ist nicht sinnlos, weil ich eine Kopie von s auf dem Stack brauche. Du kannst gerne versuchen das umzuschreiben, aber das von mir gezeigte ist IMHO die einfachste Variante in C. In einer Hochsprache würde es reichen einfach per Value nur das Array zu übergeben und immer die letzte Münze zu poppen.

Th69

Ich habe doch passenden Ideone-Code als Link angegeben.
Nenne mir doch einen Grund, warum auf den Summenwert zugegriffen werden sollte.
Wie du anhand von entsprechend geänderter Ideone-Code siehst, gibt es keinen Zugriff auf c[0] (sonst käme eine entsprechende Ausgabe).

TGGC

Klar muss der Algorithmus auf s zugreifen. Denk nochmal drüber nach.

Th69

Auf den ersten Parameter s sicherlich, aber nicht auf c[0] (bei deinem Algo und Aufruf) - und darüber reden wir doch.

TGGC

c[0] ist der erste Parameter entsprechend meiner ersten Betrachtung.