PAT L3-001. 凑零钱
原题链接
简单
作者:
青丝蛊
,
2021-04-16 16:42:27
,
所有人可见
,
阅读 273
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, m;
int v[N], f[N];
bool vis[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i];
sort(v + 1, v + n + 1, greater<int>());
for (int i = 1; i <= n; i++)
{
for (int j = m; j >= v[i]; j--)
{
if (f[j] <= f[j - v[i]] + v[i])
{
vis[i][j] = 1;
f[j] = f[j - v[i]] + v[i];
}
}
}
if (f[m] != m) puts("No Solution");
else
{
/* 打印dp路径 */
bool f = 0;
int t = m;
for (int i = n; i >= 1 && t; i--)
{
if (vis[i][t])
{
if (f) cout << ' ';
cout << v[i];
t -= v[i];
f = 1;
}
}
}
return 0;
}