algorithm - 0/1 knapsack and dynamic programming -


in http://en.wikipedia.org/wiki/knapsack_problem, dp is:

// input: // values (stored in array v) // weights (stored in array w) // number of distinct items (n) // knapsack capacity (w) j 0 w   m[0, j] := 0 end  1 n   j 0 w     if w[i] <= j       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 end 

i think switching order weight loop , number loop not impact optimal solution. right? say

for j 0 w      1 n 

thanks.

you correct. value of m[i,j] depends on values both smaller , js. situation changing lop order matters when 1 of elements can increase. example, if m[2,2] depends on m[1,3] need calculate first row comlpetely before moving second row.


Comments

Popular posts from this blog

php - regexp cyrillic filename not matches -

c# - OpenXML hanging while writing elements -

sql - Select Query has unexpected multiple records (MS Access) -