title: Dynamic Programming: 0/1 Knapsack - Retrieving Combinations as array
body: <p>I've been studying Dynamic Programming from both a bottom-up iterative approach and a top-down recursive approach using memoization.</p>
  
  <p>I've been tasked with solving the 0/1 Knapsack Problem and have successfully used the bottom-up approach but am unable to use the top-down approach.</p>
  
  <p>Using information from a webpage(<a href="http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2017%20-%20Knapsack%20Problem%20and%20Memory%20Function.htm" rel="nofollow noreferrer">http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2017%20-%20Knapsack%20Problem%20and%20Memory%20Function.htm</a>) I have come up with the following pseudocode which successfully computes the <strong>Value</strong> of the optimal solution. My issue is I cannot think of a way to keep track of the correct combination of the items which constitute this solution.</p>
  
  <pre><code>// values array containing the "profits" of each item
  // weights array containing the "weight" of each item
  // memo_pad is a list used to memoize recursive results
  values[], weights[], memo_pad[]
  
  knapsack_memoized(i, w):
      // i is the current item
      // w is the remaining weight allowed in the knapsack
  
      if memo_pad[i][w] &lt; 0: // if value not memoized
          if w &lt; weights[i]:
              memo_pad[i][w] = knapsack_memoized(i-1, w)
          else:
              memo_pad[i][w] = max{knapsack_memoized(i-1,w), values[i]+knapsack_memoized(i-1, w-weights[i])}
  
      return memo_pad[i][w]
  end
  </code></pre>
  
  <p>I cannot figure out how to find out what combination of the input items will give me the returned optimised value?</p>