If I have the following dynamic programming psudo-code for the Knapsack problem:
for w = 0 to W do V[0][w] = 0 for w = 0 to W do begin for k = 1 to n do begin if (w < w(k)) then V[k][w] = V[k - 1][w] else V[k][w] = max(V[k - 1][w],V[k - 1][w - w(k)] + v(k) end end Now becuase of the nested loops above, this code computes the array column by column (i.e. Does V[1][0] to V[n][0] then V[1][1] to V[n][1] etc.) Below I have written a code that I think should compute the array row- by-row instead (i.e. Does V[0][1] to V[0][n] then V[1][1] to V[1][n] etc): for w = 0 to W do V[w][0] = 0 for w = 0 to W do begin for k = 1 to n do begin if (w < w(k)) then V[w][k] = V[w][k - 1] else V[w][k] = max(V[w][k - 1],V[w - w(k)][k - 1] + v(k) end end Have I done this correctly so that the final result is still correct? Or is it simpler, if I simply swap the nested for loop lines so that they read: for k = 1 to n do for w = 0 to W do begin --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---