0/1 knapsack and dynamic programming

Question

In http://en.wikipedia.org/wiki/Knapsack_problem, the DP is:

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for j from 0 to W do
  m[0, j] := 0
end for 
for i from 1 to n do
  for j from 0 to W do
    if w[i] <= j then
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
    else
      m[i, j] := m[i-1, j]
    end if
  end for
end for

I think switching the order for the weight loop and the number loop does not impact the optimal solution. Is this right? Say

for j from 0 to W do
     for i from 1 to n do

Thanks.

Answer 1

You are correct. The value of m[i,j] depends only on values with both smaller is and js. The situation where changing the lop order matters is when one of the elements can increase. For example, if m[2,2] depends on m[1,3] then we need calculate the first row comlpetely before moving to the second row.