diff options
Diffstat (limited to '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'; } |