Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int nmax = 109;
- vector < vector < int > > answer , result;
- vector < int > tmp;
- int gmax , g[nmax] , n , i , j;
- void bkt(vector < int > tmp)
- {
- vector < int > sub , group;
- int m = tmp.size() , gnow;
- if (m == 0)
- {
- if (answer.size() < result.size()) result = answer;
- return;
- }
- for (int mask = 0 ; mask < (1 << m) - 1 ; ++mask)
- {
- sub.clear();
- group.clear();
- gnow = 0;
- for (int i = 0 ; i < m ; ++i)
- if ((1 << i) & mask) sub.push_back(i);
- else gnow += g[tmp[i]] , group.push_back(g[tmp[i]]);
- if (gnow <= gmax)
- {
- answer.push_back(group);
- bkt(sub);
- answer.pop_back();
- }
- }
- }
- int main()
- {
- cin >> n >> gmax;
- for (i = 0 ; i < n ; ++i)
- cin >> g[i];
- vector < int > tmp;
- for (i = 0 ; i < n ; ++i)
- tmp.push_back(i);
- result.resize(n);
- bkt(tmp);
- cout << result.size() << '\n';
- for (i = 0 ; i < result.size() ; ++i , cout << '\n')
- for (j = 0 ; j < result[i].size() ; ++j)
- cout << result[i][j] << " ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement