Algorithms : complete 01-algorithmic_toolbox 02-greedy_algorithms

1 files changed, 22 insertions, 2 deletions

diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/fractional_knapsack.cpp b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/fractional_knapsack.cpp
index 02e3fd8..7ab9b3f 100644
--- a/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/fractional_knapsack.cpp
+++ b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/fractional_knapsack.cpp
@@ -3,10 +3,30 @@
 
 using std::vector;
 
-double get_optimal_value(int capacity, vector<int> weights, vector<int> values) {
+double get_optimal_value(int capacity, vector<int> weights, vector<int> values)
+{
   double value = 0.0;
 
-  // write your code here
+  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;
 }