From 2cf6b010e0a2fb678846d7a2e9ab64d23c49bb7b Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Sun, 13 Nov 2016 19:10:05 +0100
Subject: Algorithms : complete 01-algorithmic_toolbox 02-greedy_algorithms
---
.../02-greedy_algorithms/01-change/change.cpp | 21 +++++++++++--
.../02-fractional_knapsack/fractional_knapsack.cpp | 24 +++++++++++++--
.../03-dot_product/dot_product.cpp | 22 +++++++++-----
.../04-covering_segments/covering_segments.cpp | 34 +++++++++++++++++-----
.../05-different_summands/different_summands.cpp | 16 +++++++++-
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';
}
--
cgit v1.1-2-g2b99