Raslboyy

Untitled

Aug 4th, 2019
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.79 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int main()
  9. {
  10.     ifstream fin("input.txt");
  11.     ofstream fout("output.txt");
  12.  
  13.     const int INF = 1000 * 1000 * 1000;
  14.     int n, s;
  15.     fin >> n;
  16.     vector<int> vec(n);
  17.     for (int i = 0; i < n; i++) fin >> vec[i];
  18.     fin >> s;
  19.     vector<int> ans(s+1);
  20.     ans[0] = 0;
  21.     for (int i = 1; i <= s; i++) {
  22.         ans[i] = INF;
  23.         for (int j = 0; j < n; j++)
  24.             if (vec[j] <= i)
  25.                 ans[i] = min(ans[i], ans[i - vec[j]] + 1);
  26.     }
  27.     if (ans[s] == INF) fout << "No solution" << endl;
  28.     else
  29.         while (s > 0)
  30.             for (int i = 0; i < n; i++)
  31.                 if (s >= vec[i] && ans[s] == ans[s - vec[i]] + 1) {
  32.                     fout << vec[i] << " ";
  33.                     s -= vec[i];
  34.                     break;
  35.                 }
  36.     fout << endl;
  37.  
  38.     fout.close();
  39.     fin.close();
  40.     return 0;
  41. }
Advertisement
Add Comment
Please, Sign In to add comment