Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int main()
- {
- ifstream fin("input.txt");
- ofstream fout("output.txt");
- const int INF = 1000 * 1000 * 1000;
- int n, s;
- fin >> n;
- vector<int> vec(n);
- for (int i = 0; i < n; i++) fin >> vec[i];
- fin >> s;
- vector<int> ans(s+1);
- ans[0] = 0;
- for (int i = 1; i <= s; i++) {
- ans[i] = INF;
- for (int j = 0; j < n; j++)
- if (vec[j] <= i)
- ans[i] = min(ans[i], ans[i - vec[j]] + 1);
- }
- if (ans[s] == INF) fout << "No solution" << endl;
- else
- while (s > 0)
- for (int i = 0; i < n; i++)
- if (s >= vec[i] && ans[s] == ans[s - vec[i]] + 1) {
- fout << vec[i] << " ";
- s -= vec[i];
- break;
- }
- fout << endl;
- fout.close();
- fin.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment