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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
