title: 0-1 Knapsack - Dynamic TopDown-Recursive Approach in C#
body: <p>Hello I am trying to solve the classical Knapsack problem, but so far I only managed to implement the naive recursion which works from my perspective and yields the right results:</p>
  
  <pre><code>    static int[] objValue;
      static int[] objWeight;
  
      static void Main(string[] args)
      {
          objValue = new int[] { 0, 11, 8, 4, 12, 4, 6, 9, 10 };
          objWeight = new int[] { 0, 4, 2, 2, 5, 6, 3, 5, 7 };
          int objNumber = objWert.Count() - 1;
          int maxWeight = 12;
          Console.WriteLine(Knapsack(objNumber, maxWeight));
          Console.ReadLine();
  
      }
      public static int Knapsack(int i, int w)
      {
          if (i == 0 || w==0)
          {
              return 0;
          }
  
          if(objWeight[i] &gt; w)
          {
              return Knapsack(i - 1, w);
          }
          else
          {
              int case1 = Knapsack(i - 1, w);
              int case2 = objValue[i]+Knapsack(i - 1, w - 
              objWeight[i]);
              return Math.Max(case1,case2);
          }
      } 
  </code></pre>
  
  <p>So far so good thats pretty much the basic algorithm itself, even though i get confused with the indexes sometimes. It works .... but now my dynamic approach:</p>
  
  <pre><code>    static int objNumber;
      static int maxWeight;
      static int[] objValue;
      static int[] objWeight;
      static int[,] costTable;
  
      static void Main(string[] args)
      {
          objValue = new int[] { 0, 10, 5, 7, 12, 8, 6};
          objWeight = new int[] { 0, 6, 1, 2, 5, 4, 3};
  
          objNumber = objValue.Count()-1;
          maxWeight = 10;
  
          costTable = new int[objNumber+1, maxWeight+1];
          for (int i = 0; i &lt;= objNumber; i++)
          {
              for (int w = 0; w &lt;= maxWeight; w++)
              {
                  if(i==0||w==0)
                  { costTable[i, w] = 0; }
                  else
                  costTabelle[i, w] = -1;
              }
          }
  
          int result = Knapsack(objNumber, maxWeight);
          Console.WriteLine(result);
          Console.ReadLine();
  
      }
      public static int Knapsack(int i, int w)
      {
          if (costTable[i, w] != -1)
          {
              return costTable[i, w];
          }
  
          if (i&lt;=0||w&lt;=0)
          {
              return 0;
          }
  
          if(objWeight[i] &gt; w)
          {
              costTable[i,w]=Knapsack(i - 1, w);
              return costTable[i, w];
          }
          else
          {
              int case1 = Knapsack(i - 1, w);
              int case2 = objValue[i]+Knapsack(i - 1, w - 
              objWeight[i]);
              costTable[i,w]= Math.Max(case1,case2);
              return costTable[i, w];
  
  
          }
  
      }
  </code></pre>
  
  <p>As you can see I only added a little bit of code to save all the correspondig nodes/possibilities. However it seems I made a mistake somewhere, maybe with the return function or one of the indexes, because my costTable looks like this:</p>
  
  <p><a href="https://i.stack.imgur.com/XRIhn.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/XRIhn.png" alt="LUT for knapsackproblem"></a></p>
  
  <p>There should not be any -1 in the table as far as i understood the algorithm. I hope you can provide me with some insight, looking into this since 12 hours and can not find the mistake!</p>