Hi, everybody! I try to find best solution with assignment in title. But I don't understand how I can output way of calculation. I write python program, it can output random massive and max sum, but I need way too.
from collections import deque as queue
import random
import numpy as np
array=[]
def creatArray():
r = 0
x = 5
y = 5
global array
for i in range(x):
array.append([])
for j in range(y):
array[i].append(random.randint(0,100))
r += 1
return array
creatArray()
ROW = 5
COL = 5
# Check whether given cell (row, col)
# is a valid cell or not.
def isValid(p):
# Return true if row number and column number
# is in range
return (p[0] >= 0) and (p[1] < COL)
# Function to find maximum cost to reach
# top right corner from bottom left corner
def find_max_cost(mat):
max_val = [[0 for i in range(COL)] for i in range(ROW)]
max_val[ROW - 1][0] = mat[ROW - 1][0]
# Starting po
src = [ROW - 1, 0]
# Create a queue for traversal
q = queue()
q.appendleft(src) # Enqueue source cell
# Do a BFS starting from source cell
# on the allowed direction
while (len(q) > 0):
curr = q.pop()
# Find up point
up = [curr[0] - 1, curr[1]]
# if adjacent cell is valid, enqueue it.
if (isValid(up)):
max_val[up[0]][up[1]] = max(max_val[up[0]][up[1]], mat[up[0]][up[1]] + max_val[curr[0]][curr[1]])
q.appendleft(up)
# Find right po
right = [curr[0], curr[1] + 1]
if (isValid(right)):
max_val[right[0]][right[1]] = max(max_val[right[0]][right[1]],
mat[right[0]][right[1]] + max_val[curr[0]][curr[1]])
q.appendleft(right)
# Find dig po
dig = [curr[0]-1, curr[1] + 1]
if (isValid(dig)):
max_val[dig[0]][dig[1]] = max(max_val[dig[0]][dig[1]],
mat[dig[0]][dig[1]] + max_val[curr[0]][curr[1]])
q.appendleft(dig)
# Return the required answer
return max_val[0][COL - 1]
#Driver code
print("Given matrix is ")
for i in range(ROW):
for j in range(COL):
print(array[i][j], end=" ")
print()
print("Maximum cost is ", find_max_cost(array))
I have not any ideas. Output my current code: Given matrix is 97 16 73 23 43 99 30 37 71 29 5 52 89 98 19 73 66 89 97 15 96 2 15 31 96 Maximum cost is 662
Out, which I need: Given matrix is 97 16 73 23 43 99 30 37 71 29 5 52 89 98 19 73 66 89 97 15 96 2 15 31 96 Maximum cost is 662 Way is 96-73-5-99-97-16-73-23-46
A naive solution would just be to store the route taken to achieve the max in every cell in max_value as you build the max_value array. A very ugly solution would look something like below
NOTE: the implementation below does not count for multiple valid 'way's, it will simply choose the first valid 'way' it finds. More logic would be needed to get all valid 'way's or to get a specific valid 'way' based on some criteria
from collections import deque as queue
import random
import numpy as np
array=[]
def creatArray():
r = 0
x = 5
y = 5
global array
for i in range(x):
array.append([])
for j in range(y):
array[i].append(random.randint(0,100))
r += 1
return array
creatArray()
# array = [
# [97,16,73,23,43],
# [99,30,37,71,29],
# [5,52,89,98,19],
# [73,66,89,97,15],
# [96,2,15,31,96]
# ]
ROW = 5
COL = 5
# Check whether given cell (row, col)
# is a valid cell or not.
def isValid(p):
# Return true if row number and column number
# is in range
return (p[0] >= 0) and (p[1] < COL)
# Function to find maximum cost to reach
# top right corner from bottom left corner
def find_max_cost(mat):
max_val = [[[0, []] for i in range(COL)] for i in range(ROW)]
max_val[ROW - 1][0] = [mat[ROW - 1][0], []]
# Starting po
src = [ROW - 1, 0]
# Create a queue for traversal
q = queue()
q.appendleft(src) # Enqueue source cell
# Do a BFS starting from source cell
# on the allowed direction
while (len(q) > 0):
curr = q.pop()
# Find up point
up = [curr[0] - 1, curr[1]]
# if adjacent cell is valid, enqueue it.
if (isValid(up)):
enqueue(mat, max_val, q, up, curr)
# Find right po
right = [curr[0], curr[1] + 1]
if (isValid(right)):
enqueue(mat, max_val, q, right, curr)
# Find dig po
dig = [curr[0]-1, curr[1] + 1]
if (isValid(dig)):
enqueue(mat, max_val, q, dig, curr)
# Return the required answer
max_val[0][COL - 1][1].append((0, COL-1))
return max_val[0][COL - 1]
def enqueue(mat, max_val, q, new, curr):
mvc = max_val[new[0]][new[1]][0]
mvn = mat[new[0]][new[1]] + max_val[curr[0]][curr[1]][0]
if mvn > mvc:
max_val[new[0]][new[1]][0] = mvn
l = list(max_val[curr[0]][curr[1]][1])
l.append((curr[0],curr[1]))
max_val[new[0]][new[1]][1] = l
q.appendleft(new)
#Driver code
max_cost = find_max_cost(array)
print "Maximum cost is " + str(max_cost[0])
s = ''
for t in max_cost[1]:
s = s + str(array[t[0]][t[1]]) + ' '
print "Way is " + s