title: 0/1 Knapsack Dynamic Programming Optimization, from 2D matrix to 1D matrix
body: <p>I need some clarification from wikipedia: <a href="https://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming" rel="noreferrer">Knapsack</a>, on the part</p>
  
  <blockquote>
    <p>This solution will therefore run in O(nW) time and O(nW) space. Additionally, if
    we use only a 1-dimensional array m[W] to store the current optimal values
    and pass over this array i+1 times, rewriting from m[W] to m[1] every time, we
    get the same result for only O(W) space.</p>
  </blockquote>
  
  <p>I am having trouble understanding how to turn a 2D matrix into a 1D matrix to save space. In addition, to what does <code>rewriting from m[W] to m[1] every time</code> mean (or how does it work).</p>
  
  <p>Please provide some example. Say if I have the set {V,W} --> {(5,4),(6,5),(3,2)} with K = 9. </p>
  
  <p>How would the 1D array look like?</p>