Guest User

Untitled

a guest
Dec 15th, 2017
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.86 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5.  
  6. #define CHECK_BIT(var,pos) ((var) & (1<<(pos)))
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11.  
  12. ll compare(pair <pair <ll, ll>, ll> elem1, pair <pair <ll, ll>, ll> elem2)
  13. {
  14. ll weights_diff = elem1.first.first - elem2.first.first;
  15. return weights_diff == 0 ? elem2.first.second < elem1.first.second : elem1.first.first < elem2.first.first;
  16. }
  17.  
  18. void fill_knapsack(vector <pair <ll, ll> > elements, int max_weight)
  19. {
  20. int n = elements.size();
  21. int left = n / 2;
  22. int right = n - left;
  23. ll max_cost = 0;
  24. ll ans_mask = 0;
  25. int index;
  26. vector <int> ans_indexes;
  27.  
  28. vector <pair <pair <ll, ll>, ll> > first(1 << left); // first part
  29. vector <pair <pair <ll, ll>, ll> > first_new(1 << left); // filtered first part
  30.  
  31. // cout << "first size: " << first.size() << endl;
  32.  
  33. int i;
  34. int j;
  35.  
  36. for (i = 0; i < (1 << left); ++i) // corrected, untested
  37. {
  38. first[i] = make_pair(make_pair(0, 0), i);
  39. // cout << "============ i = " << i << " ================" << endl;
  40. for (j = 0; j < left; ++j)
  41. {
  42. if (CHECK_BIT(i, j))
  43. {
  44. // cout << "j = " << j << endl;
  45. first[i].first.first += elements[j].first; // weight
  46. first[i].first.second += elements[j].second; // cost
  47. // cout << first[i].first.first << " " << first[i].first.second << endl;
  48. }
  49. }
  50. }
  51.  
  52. sort(first.begin(), first.end(), compare); // sort by weight and cost
  53.  
  54. ll best_cost = -1;
  55.  
  56. // remove subsets with less cost and greater weight
  57. for (i = 0; i < first.size(); ++i)
  58. {
  59. if (first[i].first.second <= best_cost)
  60. {
  61. first[i].second = -1;
  62. }
  63. else
  64. {
  65. best_cost = first[i].first.second;
  66. }
  67. }
  68.  
  69. int temp_diff = 0;
  70.  
  71. for (i = 0; i < first.size(); ++i)
  72. {
  73. if (first[i].second != -1)
  74. {
  75. first_new[i - temp_diff] = first[i];
  76. }
  77. else
  78. {
  79. ++temp_diff;
  80. }
  81. }
  82.  
  83. int first_size = first.size() - temp_diff;
  84.  
  85. first = first_new;
  86.  
  87. ll cur_weight = 0;
  88. ll cur_cost = 0;
  89.  
  90. int lbound, rbound, m;
  91.  
  92. for (i = 0; i < (1 << right); ++i)
  93. {
  94. cur_weight = 0;
  95. cur_cost = 0;
  96. for (j = 0; j < right; ++j)
  97. {
  98. if (CHECK_BIT(i, j))
  99. {
  100. cur_weight += elements[j + left].first;
  101. cur_cost += elements[j + left].second;
  102. }
  103. }
  104.  
  105. lbound = 0;
  106. rbound = first_size;
  107. while (lbound < rbound - 1)
  108. {
  109. m = (lbound + rbound) / 2;
  110. if (first[m].first.first <= max_weight - cur_weight)
  111. {
  112. lbound = m;
  113. }
  114. else
  115. {
  116. rbound = m;
  117. }
  118. }
  119.  
  120. index = lbound;
  121.  
  122. if (first[index].first.first + cur_weight <= max_weight && first[index].first.second + cur_cost >= max_cost)
  123. {
  124. max_cost = first[index].first.second + cur_cost;
  125. ans_mask = first[index].second + (i << left);
  126. }
  127. }
  128.  
  129. // cout << "right = " << right << endl;
  130. // cout << "ans_mask = " << ans_mask << endl;
  131.  
  132. for (j = 0; j < n; ++j)
  133. {
  134. if (CHECK_BIT(ans_mask, j))
  135. {
  136. ans_indexes.push_back(j);
  137. }
  138. }
  139.  
  140. cout << ans_indexes.size() << endl;
  141. for (int ind : ans_indexes)
  142. {
  143. cout << ind + 1 << " ";
  144. }
  145. }
  146.  
  147. int main()
  148. {
  149. int n;
  150. int max_weight;
  151.  
  152. cin >> n >> max_weight;
  153.  
  154. vector <pair <ll, ll> > elements(static_cast<unsigned int>(n));
  155.  
  156. ll cur_weight, cur_cost;
  157.  
  158. for (int i = 0; i < n; ++i)
  159. {
  160. cin >> cur_weight >> cur_cost;
  161. elements[i] = make_pair(cur_weight, cur_cost);
  162. }
  163.  
  164. fill_knapsack(elements, max_weight);
  165.  
  166. return 0;
  167. }
Add Comment
Please, Sign In to add comment