fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <vector>
  5. #include <stack>
  6. #include <stdio.h>
  7. #include <math.h>
  8. using namespace std;
  9. typedef std::vector<int> vi;
  10. typedef std::vector<pair<int, int> > vii;
  11. #define FOR(l) for(vi::iterator it=l.begin();it!=l.end();it++)
  12. #define FOR_L(l, s, e) for(vi::iterator it=l.begin()+s;it!=l.end()-e;it++)
  13.  
  14. //----------Main source code -----------------//
  15. int n, t, mSpaceLeft, sum;
  16. vi d, ans, state;
  17. void rcr(int i){
  18. 	if(i==t){
  19. 		if(n<mSpaceLeft){
  20. 			ans.clear();
  21. 			mSpaceLeft = n;
  22. 			FOR(state)
  23. 				ans.push_back(*it);
  24. 		}
  25. 		return;
  26. 	}
  27. 	//track i not chosen
  28. 	rcr(i+1);
  29. 	//or chosen
  30. 	n-=d[i];
  31. 	state.push_back(d[i]);
  32. 	if(n>=0)
  33. 	rcr(i+1);
  34. 	n+=d[i];
  35. 	state.pop_back();
  36. }
  37. int main() {
  38. 	while(cin.good()&&cin>>n){
  39. 		cin>>t;
  40. 		mSpaceLeft = 99999999;
  41. 		d.resize(t, 0);
  42. 		for(int i=0;i<t;i++)
  43. 			cin>>d[i];
  44. 		rcr(0);
  45. 		sum=0;
  46. 		FOR(ans){
  47. 			cout<<*it<<" ";
  48. 			sum+=*it;
  49. 		}
  50. 		printf("sum:%d\n", sum);
  51. 	}
  52. 	return 0;
  53. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
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
copy 
1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
43 2 sum:45
https://ideone.com/b3Ruvy
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

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!