Algorithms : complete 01-algorithmic_toolbox 02-greedy_algorithms

5 files changed, 96 insertions, 21 deletions

diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/01-change/change.cpp b/01-algorithmic_toolbox/02-greedy_algorithms/01-change/change.cpp
index e25cd67..612066b 100644
--- a/01-algorithmic_toolbox/02-greedy_algorithms/01-change/change.cpp
+++ b/01-algorithmic_toolbox/02-greedy_algorithms/01-change/change.cpp
@@ -1,8 +1,23 @@
 #include <iostream>
 
-int get_change(int n) {
-  //write your code here
-  return n;
+int get_change(int n)
+{
+    int N = 0;
+
+    while(n >= 10) {
+        n -= 10;
+        N += 1;
+    }
+    while(n >= 5) {
+        n -= 5;
+        N += 1;
+    }
+    while(n >= 1) {
+        n -= 1;
+        N += 1;
+    }
+
+    return N;
 }
 
 int main() {
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;
 }
diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/dot_product.cpp b/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/dot_product.cpp
index d9df791..f85a60a 100644
--- a/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/dot_product.cpp
+++ b/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/dot_product.cpp
@@ -4,13 +4,21 @@
 
 using std::vector;
 
-long long min_dot_product(vector<int> a, vector<int> b) {
-  // write your code here
-  long long result = 0;
-  for (size_t i = 0; i < a.size(); i++) {
-    result += a[i] * b[i];
-  }
-  return result;
+bool asc(int i, int j) { return (i < j); }
+bool desc(int i, int j) { return (i > j); }
+
+long long min_dot_product(vector<int> a, vector<int> b)
+{
+    std::sort(a.begin(), a.end(), asc);
+    std::sort(b.begin(), b.end(), desc);
+
+    long long result = 0;
+    for (size_t i = 0; i < a.size(); i++) {
+        long long x = (long long) a[i];
+        long long y = (long long) b[i];
+        result += (x * y);
+    }
+    return result;
 }
 
 int main() {
diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/covering_segments.cpp b/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/covering_segments.cpp
index c8f1fcd..9067dfe 100644
--- a/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/covering_segments.cpp
+++ b/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/covering_segments.cpp
@@ -9,14 +9,31 @@ struct Segment {
   int start, end;
 };
 
-vector<int> optimal_points(vector<Segment> &segments) {
-  vector<int> points;
-  //write your code here
-  for (size_t i = 0; i < segments.size(); ++i) {
-    points.push_back(segments[i].start);
-    points.push_back(segments[i].end);
-  }
-  return points;
+bool _sort(Segment i, Segment j)
+{
+    return (i.end <= j.end);
+}
+
+vector<int> optimal_points(vector<Segment> &segments)
+{
+    vector<int> points;
+
+    std::sort(segments.begin(), segments.end(), _sort);
+
+    while (segments.size() > 0) {
+        int v = segments.at(0).end;
+        segments.erase(segments.begin());
+        points.push_back(v);
+
+        for (std::vector<Segment>::iterator it = segments.begin() ; it != segments.end(); ) {
+            if (it->start <= v && it->end >= v) {
+                segments.erase(it);
+            } else
+                it++;
+        }
+    }
+
+    return points;
 }
 
 int main() {
@@ -31,4 +48,5 @@ int main() {
   for (size_t i = 0; i < points.size(); ++i) {
     std::cout << points[i] << " ";
   }
+  std::cout << '\n';
 }
diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/different_summands.cpp b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/different_summands.cpp
index 0f8b4cb..fe36866 100644
--- a/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/different_summands.cpp
+++ b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/different_summands.cpp
@@ -5,7 +5,20 @@ using std::vector;
 
 vector<int> optimal_summands(int n) {
   vector<int> summands;
-  //write your code here
+  int s = 0;
+  for (int i = 1; ; i++) {
+      s += i;
+      if (s == n) {
+          summands.push_back(i);
+          break;
+      }
+      if (s > n) {
+          s -= (i + i - 1);
+          summands[summands.size() - 1] = (n - s);
+          break;
+      }
+      summands.push_back(i);
+  }
   return summands;
 }
 
@@ -17,4 +30,5 @@ int main() {
   for (size_t i = 0; i < summands.size(); ++i) {
     std::cout << summands[i] << ' ';
   }
+  std::cout << '\n';
 }