本文主要是介绍L3-001 凑零钱,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 10010, M = 110;
int f[M];
int n, m;
int w[N];
int pre[N];
bool g[N][M];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
sort(w + 1, w + n + 1, [&](int a, int b) {
return a > b;
});
for (int i = 1; i <= n; i++) {
for (int j = m; j >= w[i]; j--) {
if (f[j] <= f[j - w[i]] + w[i]) {
g[i][j] = true;
f[j] = f[j - w[i]] + w[i];
}
}
}
if (f[m] != m) cout << "No Solution" << "\n";
else {
vector<int> res;
int i = n, j = m;
while (i >= 1 && j) {
if (g[i][j]) {
int t = i;
res.push_back(w[t]);
j -= w[t];
}
i--;
}
for (int k = 0; k < res.size(); k++) {
cout << res[k] << " "[k == res.size() - 1];
}
}
return 0;
}
这篇关于L3-001 凑零钱的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!