1068. Find More Coins.md

【PAT A-1068】 Find More Coins

题意概述

给出 N 个面值的硬币，问能否从中选出任意个硬币使其总面值恰好为 M？如果无解，输出No Solution。如果有多解，输出字典序最小的解。

输入输出格式

输入的第一行给出两个正整数 N 和 M。第二行给出 N 个硬币的面值。

如果不能选出任意个硬币使其总面值恰好为 M，输出No Solution；否则输出字典序最小的解。

数据规模

$$N<=10^4, M<=10^2$$

算法设计

经典的 0-1 背包动态规划问题，建议系统学习过背包动态规划之后再尝试解决本题。由于需要输出字典序最小的解，先将 N 个硬币按面值大小从大到小排序。利用dp[i][j]记录能否从前i个硬币中选出任意个硬币使其总面值为j；利用cur[i][j]表示第i个硬币能否成为组成总面值为j的解中的一个硬币。先走一趟动态规划求解dp[i][j]和cur[i][j]，再从后向前遍历cur[i][j]即可。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
#define rep(i, a, b, c) for (gg i = (a); i <= (b); i += (c))
#define rrep(i, a, b, c) for (gg i = (a); i >= (b); i -= (c))
constexpr gg MAX = 1e4 + 5;
constexpr gg MAX2 = 1e2 + 5;
constexpr gg mod = 1e9 + 7;
const gg INF = 1e18;
constexpr double thre = 1e-7;
gg ti, ni, mi, ki, di, pi, xi, yi;
gg a[MAX];
bool dp[MAX][MAX2], cur[MAX][MAX2];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> ni >> mi;
    rep(i, 1, ni, 1) { cin >> a[i]; }
    sort(begin(a) + 1, begin(a) + ni + 1, greater<gg>());
    dp[0][0] = true;
    rep(i, 1, ni, 1) {
        rep(j, 0, mi, 1) {
            dp[i][j] = dp[i - 1][j];
            if (j >= a[i] and dp[i - 1][j - a[i]]) {
                dp[i][j] = cur[i][j] = true;
            }
        }
    }
    if (not dp[ni][mi]) {
        cout << "No Solution\n";
        return 0;
    }
    rrep(i, ni, 1, 1) {
        if (cur[i][mi]) {
            cout << a[i] << (mi == a[i] ? "\n" : " ");
            mi -= a[i];
        }
    }
    return 0;
}