Skip to content

L3-001 凑零钱

Statement

Metadata

  • 作者: 陈越
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 300 ms
  • 内存限制: 64 MB

韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有 10^4 枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。

输入格式

输入第一行给出两个正整数：N（\le 10^4）是硬币的总个数，M（\le 10^2）是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。

输出格式

在一行中输出硬币的面值 V_1 \le V_2 \le \cdots \le V_k，满足条件 V_1 + V_2 + ... + V_k = M。数字间以 1 个空格分隔，行首尾不得有多余空格。若解不唯一，则输出最小序列。若无解，则输出 No Solution。

注：我们说序列{ A[1], A[2], \cdots }比{ B[1], B[2], \cdots }“小”，是指存在 k \ge 1 使得 A[i]=B[i] 对所有 i < k 成立，并且 A[k] < B[k]。

输入样例 1 

8 9
5 9 8 7 2 3 4 1

输出样例 1 

1 3 5

输入样例 2 

4 8
7 2 4 3

输出样例 2 

No Solution

Tutorial

思路：

dp[i][j] 表示前 i 个硬币能否凑出 j 元钱，转移有：

\begin{eqnarray*} dp[i][j] &= dp[i - 1][j - arr[i]] \end{eqnarray*}

最后输出答案序列的时候，先排个序，然后根据已经转移好的 dp 数组暴搜即可。

Solution

#include <ctype.h>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define CLR(a) memset(a, 0, sizeof(a))

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const double PI = 3.14159265358979323846264338327;
const double E = exp(1);
const double eps = 1e-6;

const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 5;
const int MOD = 1e9 + 7;

int arr[maxn], dp[maxn][105];
int n, m;

vector<int> v;

bool comp(int x, int y) {
    return x > y;
}

bool in_range(int x, int y) {
    if (x >= 0 && x < n && y > 0 && y <= m)
        return true;
    return false;
}

void dfs(int x, int y) {
    if (in_range(x, y)) {
        if (x == 0 && y == arr[x]) {
            v.push_back(arr[x]);
            return;
        }
        if (dp[x - 1][y - arr[x]]) {
            v.push_back(arr[x]);
            dfs(x - 1, y - arr[x]);
        } else
            dfs(x - 1, y);
    } else
        return;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    sort(arr, arr + n, comp);
    memset(dp, 0, sizeof(dp));
    if (arr[0] <= m)
        dp[0][arr[0]] = 1;
    for (int i = 0; i < n; i++) dp[i][0] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= m; j++) {
            if (arr[i] > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = (dp[i - 1][j] || dp[i - 1][j - arr[i]]);
        }
    }
    //	for (int i = 0; i < n; i++)
    //	{
    //		for (int j = 0; j <= m; j++)
    //		{
    //			if (j)
    //				printf(" ");
    //			printf("%d", dp[i][j]);
    //		}
    //		cout << endl;
    //	}
    if (dp[n - 1][m]) {
        v.clear();
        dfs(n - 1, m);
        sort(v.begin(), v.end());
        vector<int>::iterator it;
        for (it = v.begin(); it != v.end(); it++) {
            if (it != v.begin())
                printf(" ");
            cout << (*it);
        }
        cout << endl;
    } else
        printf("No Solution\n");
}
Last update: May 4, 2022
Back to top