Coins-Problem/v6.cpp at main · czarekmilek/Coins-Problem · GitHub

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main()
{
    // F, C => masa i liczba monet
    int F, C;
    cin >> F >> C;

    // p, w => tablice z nominałami i wagami monet
    vector<int> p(C + 1), w(C + 1);
    for (int i = 1; i <= C; i++)
    {
        cin >> p[i] >> w[i];
    }

    vector<int> Result(F + 1, INT_MAX);

    Result[0] = 0;

    // Indeksy użytych monet dla danej wagi
    vector<int> DP(F + 1, -1);

    // Znajdowanie minimum
    for (int f = 1; f <= F; f++)
    {
        for (int i = 1; i <= C; i++)
        {
            if (f >= w[i] && Result[f - w[i]] + p[i] < Result[f] && Result[f - w[i]] != INT_MAX)
            {
                Result[f] = Result[f - w[i]] + p[i];
                DP[f] = i;
            }
        }
    }

    // Output min
    if (Result[F] == INT_MAX)
    {
        cout << "NIE" << endl;
        return 0; // Nie trzeba patrzeć dalej, koniec
    }

    else
    {
        cout << "TAK" << endl;
        cout << Result[F] << endl;

        vector<int> coin_counts(C + 1, 0);
        int current_weight = F;
        while (current_weight > 0)
        {
            int coin_index = DP[current_weight];
            coin_counts[coin_index]++;
            current_weight -= w[coin_index];
        }

        for (int i = 1; i <= C; i++)
        {
            cout << coin_counts[i] << " ";
        }
        cout << endl;
    }

    // Znajdowanie maximum
    for (int f = 1; f <= F; f++)
    {
        for (int i = 1; i <= C; i++)
        {
            if (f >= w[i] && Result[f - w[i]] + p[i] > Result[f])
            {
                Result[f] = Result[f - w[i]] + p[i];
                DP[f] = i;
            }
        }
    }

    // Output max
    cout << Result[F] << endl;

    vector<int> coin_counts(C + 1, 0);
    int current_weight = F;
    while (current_weight > 0)
    {
        int coin_index = DP[current_weight];
        coin_counts[coin_index]++;
        current_weight -= w[coin_index];
    }

    for (int i = 1; i <= C; i++)
    {
        cout << coin_counts[i] << " ";
    }
    cout << endl;

    return 0;
}