2017阿里 运筹优化 笔试
2017阿里内推笔试题–算法工程师(运筹优化)
题目
沐哲是一个菜鸟仓库的一个拣货员，但他有非常个怪异的习惯。每次拣货的重量都要比之前拣的一个轻，每次拣到货后都可以得到1块钱，沐哲想知道这样最多能赚多少钱
32 34 7 33 21 2
13 12 3 11 26 36
16 30 22 1 24 14
20 23 25 5 19 29
27 15 9 17 31 4
6 18 8 10 35 28
沐哲可以从仓库的某个货架开始拣货，下一步可以往上走，也可以往下走，当然，向左向右也可以，但必须使得下一个货物重量减小，才会去拣。在上面的仓库中，一条可拣货的路径为 25-22-3。当然30-23-20-16-13-12-3可以拣的货更多。这也是赚钱最多的一条路径。
要求
输入行数、列数和数据矩阵，输出所赚的最大钱数。
例子:
输入:
6 6
32 34 7 33 21 2
13 12 3 11 26 36
16 30 22 1 24 14
20 23 25 5 19 29
27 15 9 17 31 4
6 18 8 10 35 28
输出:
7
分析
用一个强化学习的思路来解
设置一个dp矩阵，记录每个点的当前最大收益
遍历矩阵，对于每个点A
如果周围有仓库重量比A大的点s，且s的dp值大于等于A
用s更新a。dp(a)=dp(s)+1
复杂度是 点的数量*最长路径
row,col = 6,6 data = [[32, 34, 7, 33, 21, 2], [13, 12, 3, 11, 26, 36], [16, 30, 22, 1, 24, 14], [20, 23, 25, 5, 19, 29], [27, 15, 9, 17, 31, 4], [ 6, 18, 8, 10, 35, 28]] def isInside(row,col,i,j): return (i in range(row)) and (j in range(col)) dp=[[0 for j in range(col)] for i in range(row)] def arround(i,j): if isInside(row,col,i+1,j): if data[i+1][j]>data[i][j] and dp[i+1][j]>=dp[i][j]: return True if isInside(row,col,i-1,j): if data[i-1][j]>data[i][j] and dp[i-1][j]>=dp[i][j]: return True if isInside(row,col,i,j+1): if data[i][j+1]>data[i][j] and dp[i][j+1]>=dp[i][j]: return True if isInside(row,col,i,j-1): if data[i][j-1]>data[i][j] and dp[i][j-1]>=dp[i][j]: return True return False def max_around(i,j): t=dp[i][j] if isInside(row,col,i+1,j): if data[i+1][j]>data[i][j] and dp[i+1][j]>=dp[i][j]: t=dp[i+1][j] if isInside(row,col,i-1,j): if data[i-1][j]>data[i][j] and dp[i-1][j]>=dp[i][j]: t=dp[i-1][j] if isInside(row,col,i,j+1): if data[i][j+1]>data[i][j] and dp[i][j+1]>=dp[i][j]: t=dp[i][j+1] if isInside(row,col,i,j-1): if data[i][j-1]>data[i][j] and dp[i][j-1]>=dp[i][j]: t=dp[i][j-1] return t+1 while(1): t=0 for i in range(row): for j in range(col): if arround(i,j): dp[i][j]=max_around(i,j) t=1 if t==0: break print(max(max(dp))+1)