Algorithms : complete 01-algorithmic_toolbox 04-dynamic_programming

1 files changed, 36 insertions, 8 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
index c284560..5782461 100644
--- a/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp
+++ b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp
@@ -3,15 +3,43 @@
 
 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];
+int optimal_weight(int W, const vector<int> &w)
+{
+    int I = w.size();
+    int *m = new int[(W + 1) * (I + 1)];
+
+    int *current = &m[W + 2];
+    int *not_taken = &m[1];
+
+    // each item
+    for (int i = 1; i <= I; i++) {
+        int wi = w[i - 1];
+        for (int k = 1; k <= W; k++) {
+            if (k >= wi) {
+                int taken = *(not_taken - wi) + wi;
+                *current = ((taken > *not_taken) ? taken : *not_taken);
+            } else
+                *current = *not_taken;
+
+            current++;
+            not_taken++;
+        }
+        // skip first column
+        current++;
+        not_taken++;
     }
-  }
-  return current_weight;
+
+    /* for (int i = 0; i <= I; i++) { */
+    /*     for (int k = 0; k <= W; k++) */
+    /*         std::cout << m[(W +1) * i + k] << " "; */
+    /*     std::cout << std::endl; */
+    /* } */
+
+    int ret = *(current - 2);
+
+    delete [] m;
+
+    return ret;
 }
 
 int main() {