Algorithms : complete 05-advanced_algorithms_and_complexity 04-np-completenessalgos

7 files changed, 42 insertions, 11 deletions

diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/plan_party.cpp b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/plan_party.cpp
index 70249aa..f612252 100644
--- a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/plan_party.cpp
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/plan_party.cpp
@@ -1,5 +1,6 @@
 #include <iostream>
 #include <vector>
+#include <sys/resource.h>
 
 struct Vertex {
     int weight;
@@ -27,23 +28,39 @@ Graph ReadTree() {
     return tree;
 }
 
-void dfs(const Graph &tree, int vertex, int parent) {
-    for (int child : tree[vertex].children)
-        if (child != parent)
-            dfs(tree, child, vertex);
-
-    // This is a template function for processing a tree using depth-first search.
-    // Write your code here.
-    // You may need to add more parameters to this function for child processing.
+int dfs(const Graph &tree, int vertex, int parent, std::vector<int> &w) {
+    if ( w[vertex] == -1) {
+        if (tree[vertex].children.size() == 0) {
+            w[vertex] = tree[vertex].weight;
+        } else {
+            int m0 = tree[vertex].weight;
+            for (int child : tree[vertex].children) {
+                if (child != parent) {
+                    for (int gchild : tree[child].children) {
+                        if (gchild != child && gchild != vertex) {
+                            m0 += dfs(tree, gchild, child, w);
+                        }
+                    }
+                }
+            }
+            int m1 = 0;
+            for (int child : tree[vertex].children) {
+                if (child != parent) {
+                    m1 += dfs(tree, child, vertex, w);
+                }
+            }
+            w[vertex] = std::max(m0, m1);
+        }
+    }
+    return w[vertex];
 }
 
 int MaxWeightIndependentTreeSubset(const Graph &tree) {
     size_t size = tree.size();
     if (size == 0)
         return 0;
-    dfs(tree, 0, -1);
-    // You must decide what to return.
-    return 0;
+    std::vector<int> w(size, -1);
+    return dfs(tree, 0, -1, w);
 }
 
 int main() {
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/01 b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/01
new file mode 100644
index 0000000..4f88743
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/01
@@ -0,0 +1,2 @@
+1
+1000
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/01.a b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/01.a
new file mode 100644
index 0000000..83b33d2
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/01.a
@@ -0,0 +1 @@
+1000
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/02 b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/02
new file mode 100644
index 0000000..0777210
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/02
@@ -0,0 +1,3 @@
+2
+1 2
+1 2
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/02.a b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/02.a
new file mode 100644
index 0000000..0cfbf08
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/02.a
@@ -0,0 +1 @@
+2
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/03 b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/03
new file mode 100644
index 0000000..4867a3e
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/03
@@ -0,0 +1,6 @@
+5
+1 5 3 7 5
+5 4
+2 3
+4 2
+1 2
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/03.a b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/03.a
new file mode 100644
index 0000000..b4de394
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/tests/03.a
@@ -0,0 +1 @@
+11