題目： UVa - 11517 - Exact Change

題目說明

Unfortunate狗的ACM園地: 11517 - Exact Change

解題思路

DP 的 Coin Change 問題，核心概念為枚舉每一個最後加入的面額。需要注意的是一種面額只能使用一次，因此做的時候要從後面往前做，避免同種金額使用多次。

參考解法

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
#include <bits/stdc++.h>

using namespace std;

// reference: https://ppt.cc/fp0yAx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

const int INF = (int)1e9;

int N, P;
int sum;
int C[101];
int dp[20001];

void init()
{
    for (int i = 1; i <= sum; ++i) dp[i] = INF;
}

void read()
{
    cin >> P >> N;
    sum = 0; // 一種面額只能用一次，紀錄最多需要做到多少錢
    for (int i = 0; i < N; ++i)
    {
        cin >> C[i];
        if (sum < P) sum += C[i];
    }
}

void CoinChange()
{
    for (int i = 0; i < N; ++i)
    {
        // 反向做，避免多次使用相同的面額
        for (int j = sum; j >= C[i]; --j) dp[j] = min(dp[j - C[i]] + 1, dp[j]);
    }
}

void solve()
{
    int p = P;
    while (p < sum && dp[p] == INF) ++p;
    cout << p << ' ' << dp[p] << '\n';
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        read();
        init();
        CoinChange();
        solve();
    }
}

參考資料

Unfortunate狗的ACM園地: 11517 - Exact Change
UVa 11517 - Exact Change_小白菜又菜-CSDN博客