Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- #define CHECK_BIT(var,pos) ((var) & (1<<(pos)))
- using namespace std;
- typedef long long ll;
- ll compare(pair <pair <ll, ll>, ll> elem1, pair <pair <ll, ll>, ll> elem2)
- {
- ll weights_diff = elem1.first.first - elem2.first.first;
- return weights_diff == 0 ? elem2.first.second < elem1.first.second : elem1.first.first < elem2.first.first;
- }
- void fill_knapsack(vector <pair <ll, ll> > elements, int max_weight)
- {
- int n = elements.size();
- int left = n / 2;
- int right = n - left;
- ll max_cost = 0;
- ll ans_mask = 0;
- int index;
- vector <int> ans_indexes;
- vector <pair <pair <ll, ll>, ll> > first(1 << left); // first part
- vector <pair <pair <ll, ll>, ll> > first_new(1 << left); // filtered first part
- // cout << "first size: " << first.size() << endl;
- int i;
- int j;
- for (i = 0; i < (1 << left); ++i) // corrected, untested
- {
- first[i] = make_pair(make_pair(0, 0), i);
- // cout << "============ i = " << i << " ================" << endl;
- for (j = 0; j < left; ++j)
- {
- if (CHECK_BIT(i, j))
- {
- // cout << "j = " << j << endl;
- first[i].first.first += elements[j].first; // weight
- first[i].first.second += elements[j].second; // cost
- // cout << first[i].first.first << " " << first[i].first.second << endl;
- }
- }
- }
- sort(first.begin(), first.end(), compare); // sort by weight and cost
- ll best_cost = -1;
- // remove subsets with less cost and greater weight
- for (i = 0; i < first.size(); ++i)
- {
- if (first[i].first.second <= best_cost)
- {
- first[i].second = -1;
- }
- else
- {
- best_cost = first[i].first.second;
- }
- }
- int temp_diff = 0;
- for (i = 0; i < first.size(); ++i)
- {
- if (first[i].second != -1)
- {
- first_new[i - temp_diff] = first[i];
- }
- else
- {
- ++temp_diff;
- }
- }
- int first_size = first.size() - temp_diff;
- first = first_new;
- ll cur_weight = 0;
- ll cur_cost = 0;
- int lbound, rbound, m;
- for (i = 0; i < (1 << right); ++i)
- {
- cur_weight = 0;
- cur_cost = 0;
- for (j = 0; j < right; ++j)
- {
- if (CHECK_BIT(i, j))
- {
- cur_weight += elements[j + left].first;
- cur_cost += elements[j + left].second;
- }
- }
- lbound = 0;
- rbound = first_size;
- while (lbound < rbound - 1)
- {
- m = (lbound + rbound) / 2;
- if (first[m].first.first <= max_weight - cur_weight)
- {
- lbound = m;
- }
- else
- {
- rbound = m;
- }
- }
- index = lbound;
- if (first[index].first.first + cur_weight <= max_weight && first[index].first.second + cur_cost >= max_cost)
- {
- max_cost = first[index].first.second + cur_cost;
- ans_mask = first[index].second + (i << left);
- }
- }
- // cout << "right = " << right << endl;
- // cout << "ans_mask = " << ans_mask << endl;
- for (j = 0; j < n; ++j)
- {
- if (CHECK_BIT(ans_mask, j))
- {
- ans_indexes.push_back(j);
- }
- }
- cout << ans_indexes.size() << endl;
- for (int ind : ans_indexes)
- {
- cout << ind + 1 << " ";
- }
- }
- int main()
- {
- int n;
- int max_weight;
- cin >> n >> max_weight;
- vector <pair <ll, ll> > elements(static_cast<unsigned int>(n));
- ll cur_weight, cur_cost;
- for (int i = 0; i < n; ++i)
- {
- cin >> cur_weight >> cur_cost;
- elements[i] = make_pair(cur_weight, cur_cost);
- }
- fill_knapsack(elements, max_weight);
- return 0;
- }
Add Comment
Please, Sign In to add comment