Adott S pénzösszeg, továbbá n darab természetes szám, amik banjegyek címleteinek az értékei.

Állítsuk elő az összes kifizetési módot az adott típusú bankjegyekkel (sorrend nem számít).

Példa

    S = 17
    n = 4
    bankjegyek: 1 5 10 20

kimenet:
    1 1 1 .... 1  (17 db)
    5 1 ... 1 (12 db)
    5 5 1 ... 1 (7 db)
    5 5 5 1 1
    10 1 1 .. 1 (7db)
    10 5 1 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <fstream>
using namespace std;

void general(
    int szint, int s, int megoldas[],
    int n, int bankjegyek[])
{
    if (s == 0) {
        for (int i = 0; i < szint; i++)
            cout << megoldas[i] << " ";
        cout << endl;
    }
    else {
        for (int i = 0; i < n; i++) {
            int ertek = bankjegyek[i];

            if (ertek <= s
                && (szint == 0 || megoldas[szint-1] >= ertek))
            {
                megoldas[szint] = ertek;
                general(szint+1, s-ertek, megoldas, n, bankjegyek);
            }
        }

    }
}

int main()
{
    int s;
    cin >> s;

    int n;
    cin >> n;

    int bankjegyek[1000];
    for (int i = 0; i < n; i++)
        cin >> bankjegyek[i];

    int megoldas[1000];

    general(0, s, megoldas, n, bankjegyek);

    return 0;
}

Ugyanaz, de sorszámozva a megoldásokat:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <fstream>
using namespace std;

void general(
    int szint, int s, int megoldas[], int &db,
    int n, int bankjegyek[])
{
    if (s == 0) {
        db++;
        cout << db << ". ";

        for (int i = 0; i < szint; i++)
            cout << megoldas[i] << " ";
        cout << endl;
    }
    else {
        for (int i = 0; i < n; i++) {
            int ertek = bankjegyek[i];

            if (ertek <= s
                && (szint == 0 || megoldas[szint-1] >= ertek))
            {
                megoldas[szint] = ertek;
                general(szint+1, s-ertek, megoldas, db, n, bankjegyek);
            }
        }

    }
}

int main()
{
    int s;
    cin >> s;

    int n;
    cin >> n;

    int bankjegyek[1000];
    for (int i = 0; i < n; i++)
        cin >> bankjegyek[i];

    int megoldas[1000];
    int db = 0;

    general(0, s, megoldas, db, n, bankjegyek);

    return 0;
}

HF.

Oldjuk meg úgy, hogy adott a bemeneten még az is, hogy egy címletből legfeljebb hányat használhatunk!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <fstream>
using namespace std;

void general(
    int szint, int s, int megoldas[], int &db,
    int n, int bankjegyek[], int limit[])
{
    if (s == 0) {
        db++;
        cout << db << ". ";

        for (int i = 0; i < szint; i++)
            cout << megoldas[i] << " ";
        cout << endl;
    }
    else {
        for (int i = 0; i < n; i++) {
            int ertek = bankjegyek[i];

            if (ertek <= s && limit[i] > 0
                && (szint == 0 || megoldas[szint-1] >= ertek))
            {
                limit[i]--;
                megoldas[szint] = ertek;
                general(szint+1, s-ertek, megoldas, db, n, bankjegyek, limit);
                limit[i]++;
            }
        }

    }
}

int main()
{
    int s;
    cin >> s;

    int n;
    cin >> n;

    int bankjegyek[1000];
    for (int i = 0; i < n; i++)
        cin >> bankjegyek[i];


    int limit[1000];
    for (int i = 0; i < n; i++)
        cin >> limit[i];

    int megoldas[1000];
    int db = 0;

    general(0, s, megoldas, db, n, bankjegyek, limit);

    return 0;
}