diff options
Diffstat (limited to '01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack')
5 files changed, 37 insertions, 0 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 new file mode 100644 index 0000000..02e3fd8 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/fractional_knapsack.cpp @@ -0,0 +1,29 @@ +#include <iostream> +#include <vector> + +using std::vector; + +double get_optimal_value(int capacity, vector<int> weights, vector<int> values) { + double value = 0.0; + + // write your code here + + 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; +} diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/01 b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/01 new file mode 100644 index 0000000..0094f93 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/01 @@ -0,0 +1,4 @@ +3 50 +60 20 +100 50 +120 30 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/01.a b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/01.a new file mode 100644 index 0000000..3af99ee --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/01.a @@ -0,0 +1 @@ +180 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/02 b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/02 new file mode 100644 index 0000000..762e5ef --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/02 @@ -0,0 +1,2 @@ +1 10 +500 30 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/02.a b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/02.a new file mode 100644 index 0000000..53ed09b --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/02.a @@ -0,0 +1 @@ +166.6666667 |