01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/fractional_knapsack.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <iostream>
#include <vector>

using std::vector;

double get_optimal_value(int capacity, vector<int> weights, vector<int> values)
{
  double value = 0.0;

  while ((capacity > 0) && (weights.size() > 0)) {
      int idx = 0;
      double ratio = 0.0;
      for (int i = 0; i < weights.size(); i++) {
          double r = ((double) values.at(i)) / weights.at(i);
          if (r > ratio) {
              idx = i;
              ratio = r;

          }
      }
      double a = capacity;
      if (weights[idx] < capacity)
          a = weights[idx];

      value += (ratio * a);
      capacity -= a;
      weights.erase(weights.begin()+idx);
      values.erase(values.begin()+idx);
  }

  return value;
}

int main() {
  int n;
  int capacity;
  std::cin >> n >> capacity;
  vector<int> values(n);
  vector<int> weights(n);
  for (int i = 0; i < n; i++) {
    std::cin >> values[i] >> weights[i];
  }

  double optimal_value = get_optimal_value(capacity, weights, values);

  std::cout.precision(10);
  std::cout << optimal_value << std::endl;
  return 0;
}