CODEWITHSUNDEEP
algorithmknapsack-problem
Dhruv Mullick
Dhruv Mullick

Reputation: 561

Can Knapsack algorithms be implemented in Column major form?

I searched for Knapsack algorithm on the net, and in all the implementations, I saw that the 2D array is of the form:

 int K[n+1][W+1];

where n is the number of elements and W is the maximum weight which can be accommodated in the Knapsack.

This array was filled in a bottom up manner, in a row major format. Can it even be done in a column major format?

Upvotes: 0

Views: 34

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65478

Roughly the only requirement on the order in which the array is filled is that, if a <= b and c <= d, then the (a,c) cell is not filled after the (b,d) cell. This follows from tracing the data dependencies of the dynamic program. Row-major, column-major, and many other fill orders are possible.

Upvotes: 1

Related Questions