Guest User

Untitled

a guest
Nov 16th, 2018
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using std::vector;
  5.  
  6. int get_max_unit_value_item_index(vector<double> weights, vector<double> values){
  7. int max_index;
  8. double max_unit_value = 0.0;
  9. for (size_t i = 0; i < weights.size(); i++){
  10. if (weights[i] == 0 ) continue;
  11. double unit_value = values[i] / weights[i];
  12. if (unit_value > max_unit_value) {
  13. max_unit_value = unit_value;
  14. max_index = i;
  15. }
  16. }
  17. //if weights and values are depleted
  18. if (!max_unit_value) return -1;
  19. return max_index;
  20. }
  21.  
  22. double min(double a, double b){
  23. if (a>b){
  24. return b;
  25. } else {return a;}
  26. }
  27.  
  28. double get_optimal_value(double capacity, vector<double> weights, vector<double> values) {
  29. double value = 0.0;
  30. int max_index;
  31. double value_to_take;
  32. double units_to_take;
  33. double units_available;
  34. while (capacity){
  35. max_index = get_max_unit_value_item_index(weights, values);
  36. //when there's no max index, inventory depleted
  37. if (max_index==-1) break;
  38. units_available = weights[max_index];
  39. units_to_take = min(units_available, capacity);
  40. value_to_take = units_to_take * values[max_index] / weights[max_index];
  41. value += value_to_take;
  42.  
  43. weights[max_index] -= units_to_take;
  44. values[max_index] -= value_to_take;
  45. capacity -= units_to_take;
  46. }
  47.  
  48.  
  49.  
  50. return value;
  51. }
  52.  
  53. int main() {
  54. int n;
  55. double capacity;
  56. std::cin >> n >> capacity;
  57. vector<double> values(n);
  58. vector<double> weights(n);
  59. for (int i = 0; i < n; i++) {
  60. std::cin >> values[i] >> weights[i];
  61. }
  62.  
  63. double optimal_value = get_optimal_value(capacity, weights, values);
  64.  
  65. std::cout.precision(10);
  66. std::cout << optimal_value << std::endl;
  67. return 0;
  68. }
Add Comment
Please, Sign In to add comment