Algorithms : add 01-algorithmic_toolbox 04-dynamic_programming

3 files changed, 28 insertions, 0 deletions

diff --git a/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp
new file mode 100644
index 0000000..c284560
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp
@@ -0,0 +1,25 @@
+#include <iostream>
+#include <vector>
+
+using std::vector;
+
+int optimal_weight(int W, const vector<int> &w) {
+  //write your code here
+  int current_weight = 0;
+  for (size_t i = 0; i < w.size(); ++i) {
+    if (current_weight + w[i] <= W) {
+      current_weight += w[i];
+    }
+  }
+  return current_weight;
+}
+
+int main() {
+  int n, W;
+  std::cin >> W >> n;
+  vector<int> w(n);
+  for (int i = 0; i < n; i++) {
+    std::cin >> w[i];
+  }
+  std::cout << optimal_weight(W, w) << '\n';
+}
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01 b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01
new file mode 100644
index 0000000..3fa3706
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01
@@ -0,0 +1,2 @@
+10 3
+1 4 8
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01.a b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01.a
new file mode 100644
index 0000000..ec63514
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01.a
@@ -0,0 +1 @@
+9