Advertisement
Guest User

Untitled

a guest
Sep 27th, 2016
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.15 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int nmax = 109;
  6.  
  7. vector < vector < int > > answer , result;
  8. vector < int > tmp;
  9. int gmax , g[nmax] , n , i , j;
  10.  
  11. void bkt(vector < int > tmp)
  12. {
  13. vector < int > sub , group;
  14. int m = tmp.size() , gnow;
  15.  
  16. if (m == 0)
  17. {
  18. if (answer.size() < result.size()) result = answer;
  19. return;
  20. }
  21.  
  22. for (int mask = 0 ; mask < (1 << m) - 1 ; ++mask)
  23. {
  24. sub.clear();
  25. group.clear();
  26. gnow = 0;
  27.  
  28. for (int i = 0 ; i < m ; ++i)
  29. if ((1 << i) & mask) sub.push_back(i);
  30. else gnow += g[tmp[i]] , group.push_back(g[tmp[i]]);
  31.  
  32. if (gnow <= gmax)
  33. {
  34. answer.push_back(group);
  35. bkt(sub);
  36. answer.pop_back();
  37. }
  38. }
  39. }
  40.  
  41. int main()
  42. {
  43.  
  44. cin >> n >> gmax;
  45. for (i = 0 ; i < n ; ++i)
  46. cin >> g[i];
  47.  
  48. vector < int > tmp;
  49. for (i = 0 ; i < n ; ++i)
  50. tmp.push_back(i);
  51.  
  52. result.resize(n);
  53. bkt(tmp);
  54.  
  55. cout << result.size() << '\n';
  56. for (i = 0 ; i < result.size() ; ++i , cout << '\n')
  57. for (j = 0 ; j < result[i].size() ; ++j)
  58. cout << result[i][j] << " ";
  59.  
  60. return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement