nrworld
Newbie level 1
Matrix Sum Maximization
A 16x16 matrix is randomly filled with natural numbers between 10 and 80. Suggest an algorithm to identify a continuous path through any 50 of the 256 numbers entered in the matrix such that the total score is maximum.
Your line may start and finish anywhere, but must not cross itself. Only vertical and horizontal lines are allowed (no diagonal lines)
Output should be in the form of a list of cells, the path through which results in maximum total score.
Example:
An example matrix and a continuous path through 50 gray colored boxes are shown below. (See Attachment)
The output for describing the path would be (1,1); (2,1); (2,2); (2,3); (3,3); (4,3)…………
For this example matrix, the highlighted path yields a score of 2583
A 16x16 matrix is randomly filled with natural numbers between 10 and 80. Suggest an algorithm to identify a continuous path through any 50 of the 256 numbers entered in the matrix such that the total score is maximum.
Your line may start and finish anywhere, but must not cross itself. Only vertical and horizontal lines are allowed (no diagonal lines)
Output should be in the form of a list of cells, the path through which results in maximum total score.
Example:
An example matrix and a continuous path through 50 gray colored boxes are shown below. (See Attachment)
The output for describing the path would be (1,1); (2,1); (2,2); (2,3); (3,3); (4,3)…………
For this example matrix, the highlighted path yields a score of 2583