T4 自动兑换机

· · 题解

题目链接

本题是纸币找零问题，与完全背包问题有相似之处。转换为美分后，需要兑换的纸币数量对应背包的容量，不同种类的硬币对应着不同的物品，硬币的面值对应着物品的价值，不过与标准的完全背包问题不同的是，此处所求的并不是背包能够达到的最大价值，而是求恰能够将背包装满时所使用的最少物品数量即具体的物品数量构成。

最少找零问题可以通过动态规划予以解决。给定一组面值 D=<d_1,\ d_2,\ …,\ d_n>，面值按递增排列（不是必须的，只是为了描述问题方便），满足d_i < d_i+1(1 \leq i < n)，d_1 是该纸币系统的“最小单元”，即对于任意零钱 X，都可以通过有限个 d_1 进行找零（如人民币中的 1 分面值），否则将出现某些特定零钱无法找零的情况（如果人民币不存在 1 分的零钱，则找 1 分零钱时存在困难）。设找零钱 X 的最少张数为 C(X)，若要找的零钱数为 M，则所求为 C(M)，因为最后找的一张零钱必定是给定面值中的一种，那么只要知道了 C(M-d_1)，C(M-d_2)，…，C(M-d_i)，其最小值再加一即为 C(M)，而只要知道了 C(M-d_1-d_1)，C(M-d_1-d_2)，…，C(M-d_1-d_i)，其最小值再加一即为 C(M-d_1)……。故此问题的递推关系为

C(M)=\operatorname{min}\{C(M-d_i) + 1\}, \ 1 \leq i \leq n, \ C(0)=0

很显然，在初始化的时候，找 0 元零钱需要的最少纸币张数为 0，因此有 C(0)=0。

由于需输出最少硬币方案的具体构成，因此在自底向上进行动态规划时需要记录每一次选择时的相关参数，以便重建选择路径时使用。

以下是暂不考虑方案字典序最小时的解题方案。

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int n;
int denom[110];
int coins[10010], parent[10010], idx[10010], cnt[110];

void findPath(int money)
{
    if (money > 0)
    {
        cnt[idx[money]]++;
        findPath(parent[money]);
    }
}

void findMiniumCoins(int money)
{
    fill(coins, coins + 10010, INF);
    fill(cnt, cnt + 110, 0);

    coins[0] = 0;
    for (int m = 1; m <= money; m++)
    {
        int minCoins = INF, minIdx = INF;
        for (int d = 0; d < n; d++)
            if (m >= denom[d] && coins[m - denom[d]] != INF &&
                minCoins > (coins[m - denom[d]] + 1))
                minCoins = coins[m - denom[d]] + 1, minIdx = d;

        if (minIdx != INF)
        {
            coins[m] = minCoins;
            parent[m] = m - denom[minIdx];
            idx[m] = minIdx;
        }
    }

    if (coins[money] == INF)
        cout << "No solution." << endl;
    else
    {
        cout << coins[money];

        findPath(money);

        int plusPrinted = 0;
        for (int i = 0; i < n; i++)
            if (cnt[i] > 0)
            {
                cout << (plusPrinted++ ? "+" : " ");
                cout << denom[i] << "*" << cnt[i];
            }
        cout << endl;
    }
}

int main(int argc, char *argv[])
{
    double money;
    int cases;
    cin >> cases;
    for (int cs = 1; cs <= cases; cs++)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> denom[i];

        sort(denom, denom + n);
        n = unique(denom, denom + n) - denom;

        cin >> money;
        findMiniumCoins((int)(money * 100.0 + 0.5));
    }

    return 0;
}

可以证明：对给定的面值按递增排序，去除重复值，如果满足 d_i \leq 2 \times d_{i+1}（1 \leq i \lt c），则兑换序列必定唯一。测试点 1 包含的测试数据均是具有唯一兑换方案的测试数据，使用上述代码即可获得 \operatorname{Accepted}。

但是对于不满足上述性质的硬币面值序列，可能存在多种的兑换方案，使用上述代码得到的可能并不是正确答案。此时可以考虑对面值按照字典序进行排列，先使用字典序小的面值进行兑换，得到以下代码。

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int n;
int denom[110];
int coins[10010], parent[10010], idx[10010], cnt[110];

void findPath(int money)
{
    if (money > 0)
    {
        cnt[idx[money]]++;
        findPath(parent[money]);
    }
}

void findMiniumCoins(int money)
{
    fill(coins, coins + 10010, INF);
    fill(cnt, cnt + 110, 0);

    coins[0] = 0;
    for (int m = 1; m <= money; m++)
    {
        int minCoins = INF, minIdx = INF;
        for (int d = 0; d < n; d++)
            if (m >= denom[d] && coins[m - denom[d]] != INF &&
                minCoins > (coins[m - denom[d]] + 1))
                minCoins = coins[m - denom[d]] + 1, minIdx = d;

        if (minIdx != INF)
        {
            coins[m] = minCoins;
            parent[m] = m - denom[minIdx];
            idx[m] = minIdx;
        }
    }

    if (coins[money] == INF)
        cout << "No solution." << endl;
    else
    {
        cout << coins[money];

        findPath(money);

        map<int, int> output;
        for (int i = 0; i < n; i++)
            if (cnt[i])
                output[denom[i]] = cnt[i];
        int plusPrinted = 0;
        for (auto p : output)
        {
            cout << (plusPrinted++ ? "+" : " ");
            cout << p.first << "*" << p.second;
        }
        cout << endl;
    }
}

int cmp(int a, int b)
{
    return to_string(a) < to_string(b);
}

int main(int argc, char *argv[])
{
    double money;
    int cases;
    cin >> cases;
    for (int cs = 1; cs <= cases; cs++)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> denom[i];

        sort(denom, denom + n, cmp);
        n = unique(denom, denom + n) - denom;

        cin >> money;
        findMiniumCoins((int)(money * 100.0 + 0.5));
    }

    return 0;
}

对于上述使用简单排序后再进行动态规划的方法，虽然考虑到了面值字典序大小对方案字典序大小的影响，但是未考虑到硬币个数、* 符号、+ 符号对方案字典序大小的影响（测试点 2 包含的均是使用上述简单排序后在进行动态规划就可获得 \operatorname{Accepted} 的数据。）。例如以下的测试数据：

1
11 304 399 203 268 173 76 39 241 266 18 393 7.63

使用前述代码的输出为：

4 18*1+173*2+399*1

但正确的输出为：

4 18*1+173*1+268*1+304*1

基于以上原因，必须在动态规划过程中记录每种具有最小硬币数量的兑换方案，最后使用回溯来搜索具有最小字典序的兑换方案。以下是一种使用 \operatorname{STL} 的“偷懒”实现。

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int n, denom[110], coins[10010];
vector<int> parent[10010];
map<int, int> path, best;

void dfs(int money)
{
    if (money > 0)
    {
        if (best.size())
        {
            auto it1 = path.begin(), it2 = best.begin();
            for (int i = 0; i < path.size() - 1; i++)
            {
                string s1 = to_string(it1->first) + '*' + to_string(it1->second);
                string s2 = to_string(it2->first) + '*' + to_string(it2->second);
                if (s1 != s2)
                {
                    if (s1 > s2) return;
                    break;
                }
                it1++, it2++;
            }
        }
        for (auto m : parent[money])
        {
            if (path.size() && m < path.rbegin()->first) continue;
            path[m]++;
            dfs(money - m);
            path[m]--;
            if (!path[m]) path.erase(m);
        }
    }
    else
    {
        if (best.size())
        {
            auto it1 = path.begin(), it2 = best.begin();
            for (int i = 0; i < path.size(); i++)
            {
                string s1 = to_string(it1->first) + '*' + to_string(it1->second);
                string s2 = to_string(it2->first) + '*' + to_string(it2->second);
                if (s1 != s2)
                {
                    if (s1 > s2) return;
                    break;
                }
                it1++, it2++;
            }
        }
        best = path;
    }
}

void dp(int money)
{
    for (int i = 0; i <= money; i++) parent[i].clear();
    coins[0] = 0;
    for (int i = 1; i <= money; i++)
    {
        coins[i] = INF;
        for (int j = 0; j < n; j++)
            if (i >= denom[j] && coins[i - denom[j]] != INF)
            {
                if (coins[i] > coins[i - denom[j]] + 1)
                {
                    coins[i] = coins[i - denom[j]] + 1;
                    parent[i].clear();
                    parent[i].push_back(denom[j]);
                }
                else if (coins[i] == coins[i - denom[j]] + 1)
                {
                    parent[i].push_back(denom[j]);
                }
            }
    }

    if (coins[money] == INF) cout << "No solution." << endl;
    else
    {
        path.clear();
        best.clear();
        dfs(money);
        cout << coins[money] << ' ';
        bool plus = false;
        for (auto p : best)
        {
            if (plus) cout << '+';
            cout << p.first << '*' << p.second;
            plus = true;
        }
        cout << '\n';
    }
}

int main(int argc, char *argv[])
{
    int cases;
    cin >> cases;
    for (int cs = 1; cs <= cases; cs++)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> denom[i];
        sort(denom, denom + n);
        n = unique(denom, denom + n) - denom;
        double money;
        cin >> money;
        dp((int)(money * 100.0 + 0.5));
    }
    return 0;
}

但是由于上述代码使用 \operatorname{STL} 较多，而本题并未开启 \operatorname{O_2} 优化，因此对于后面几个测试点会发生超时，需要自行优化，以下是一种可行的 \operatorname{Accepted} 代码。

附注：基于 Macesuted 的建议，卡 \operatorname{STL} 对参赛者并不友好，因此下调了测试数据的组数，同时提高了时限到 2.0s，所以使用 \operatorname{STL} 的前述实现也可以通过本题。

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int n, denom[110], coins[10010];
int parent[10010][110], parentCnt[10010];
int path[10010], best[10010];
int pathCnt[10010], bestCnt[10010];
int pathTotal, bestTotal;

void dfs(int money)
{
    if (money > 0)
    {
        if (bestTotal)
        {
            for (int i = 0; i < pathTotal - 1; i++)
            {
                if (path[i] != best[i])
                {
                    if (to_string(path[i]) > to_string(best[i])) return;
                    break;
                }

                if (pathCnt[i] != bestCnt[i])
                {
                    if (to_string(pathCnt[i]) > to_string(bestCnt[i])) return;
                    break;
                }
            }
        }

        for (int i = 0; i < parentCnt[money]; i++)
        {
            int m = parent[money][i];
            if (pathTotal && m < path[pathTotal - 1]) continue;
            if (m == path[pathTotal -1]) pathCnt[pathTotal - 1]++;
            else path[pathTotal] = m, pathCnt[pathTotal]++, pathTotal++;
            dfs(money - m);
            pathCnt[pathTotal - 1]--;
            if (pathCnt[pathTotal - 1] == 0)
            pathTotal--;
        }
    }
    else
    {

        if (bestTotal)
        {
            for (int i = 0; i < pathTotal; i++)
            {
                if (path[i] != best[i])
                {
                    if (to_string(path[i]) > to_string(best[i])) return;
                    break;
                }

                if (pathCnt[i] != bestCnt[i])
                {
                    if (to_string(pathCnt[i]) > to_string(bestCnt[i])) return;
                    break;
                }
            }
        }

        bestTotal = pathTotal;
        for (int i = 0; i < pathTotal; i++)
            best[i] = path[i], bestCnt[i] = pathCnt[i];
    }
}

void dp(int money)
{
    for (int i = 0; i <= money; i++) parentCnt[i] = 0;
    coins[0] = 0;
    for (int i = 1; i <= money; i++)
    {
        coins[i] = INF;
        for (int j = 0; j < n; j++)
            if (i >= denom[j] && coins[i - denom[j]] != INF)
            {
                if (coins[i] > coins[i - denom[j]] + 1)
                {
                    coins[i] = coins[i - denom[j]] + 1;
                    parentCnt[i] = 0;
                    parent[i][parentCnt[i]++] = denom[j];
                }
                else if (coins[i] == coins[i - denom[j]] + 1)
                {
                    parent[i][parentCnt[i]++] = denom[j];
                }
            }
    }

    if (coins[money] == INF) cout << "No solution." << endl;
    else
    {
        bestTotal = pathTotal = 0;
        memset(bestCnt, 0, sizeof bestCnt);
        memset(pathCnt, 0, sizeof pathCnt);
        dfs(money);
        cout << coins[money] << ' ';
        bool plus = false;
        for (int i = 0; i < bestTotal; i++)
        {
            if (plus) cout << '+';
            cout << best[i] << '*' << bestCnt[i];
            plus = true;
        }
        cout << '\n';
    }
}

int main(int argc, char *argv[])
{
    int cases;
    cin >> cases;
    for (int cs = 1; cs <= cases; cs++)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> denom[i];
        sort(denom, denom + n);
        n = unique(denom, denom + n) - denom;
        double money;
        cin >> money;
        dp((int)(money * 100.0 + 0.5));
    }
    return 0;
}