fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl '\n'
  5. #define ll long long
  6.  
  7. int n, target, ans_sum=0;
  8. vector<int> num, temp, ans;
  9.  
  10. void print(){
  11.   for(auto &x: ans)
  12.     cout << x << ' ';
  13.  
  14.   cout << "sum:" << ans_sum << '\n';
  15. }
  16.  
  17. void solve(int i, int sum){
  18.   // Base
  19.   if(i == n){
  20.     if(sum >= ans_sum) {
  21.       if (sum > ans_sum) {
  22.         ans_sum = sum;
  23.         ans = temp;
  24.       } else {
  25.         if (temp.size() > ans.size()) {
  26.           ans = temp;
  27.         }
  28.       }
  29.     }
  30.     return;
  31.   }
  32.   // Transition
  33.   if(sum+num[i] <= target){
  34.     temp.push_back(num[i]);
  35.  
  36.     solve(i+1, sum+num[i]);
  37.  
  38.     temp.pop_back();
  39.   }
  40.  
  41.   solve(i+1, sum);
  42. }
  43.  
  44.  
  45. int main(){
  46.   ios::sync_with_stdio(false);
  47.   cin.tie(nullptr), cout.tie(nullptr);
  48.  
  49.   while(cin >> target){
  50.     cin >> n;
  51.     for (int i = 0; i < n; ++i) {
  52.       int value;cin >> value;
  53.       num.push_back(value);
  54.     }
  55.     solve(0, 0);
  56.     print();
  57.  
  58.     ans.clear(); num.clear(); ans_sum=0;
  59.   }
  60.   return 0;
  61. }
  62.  
  63.  
  64.  
  65. // ####################
  66. // ##### 3BcarenO #####
  67. // ####################
Success #stdin #stdout 0.01s 5460KB
comments (?)
stdin 
5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2
stdout 
1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45
https://ideone.com/h5c1FA
UVA - CD (624)
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!